enter search term and/or author name
Among a set of n coins of two weights (good and bad), and using a balance, we wish to determine the number of bad coins using as few measurements as possible. There is a known adaptive decision tree that answers this question in...
Solvable Group Isomorphism Is (Almost) in NP ∩ coNP
Vikraman Arvind, Jacobo Torán
Article No.: 4
The Group Isomorphism problem consists in deciding whether two input groups G1 and G2 given by their multiplication tables are isomorphic. We first give a 2-round Arthur-Merlin protocol for the Group...
A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems
Michael R. Fellows, Jiong Guo, Hannes Moser, Rolf Niedermeier
Article No.: 5
We investigate the computational complexity of a general “compression task” centrally occurring in the recently developed technique of iterative compression for exactly solving NP-hard minimization problems. The core issue...