CJTCS Volume 1999 Abstracts

  1. On Finding the Number of Graph Automorphisms by Robert Beals, Richard Chang, William Gasarch, and Jacobo Torán, 10 February 1999

    In computational complexity theory, a function f is called b(n) -enumerable if there exists a polynomial-time function that can restrict the output of f(x) to one of b(n) possible values. This paper investigates #GA, the function that computes the number of automorphisms of an undirected graph, and GI, the set of pairs of isomorphic graphs. The results in this paper show the following connections between the enumerability of #GA and the computational complexity of GI.

    1. #GA is e^(O(sqrt(n log n))) -enumerable}.
    2. If #GA is polynomially enumerable, then GI in R.
    3. For epsilon < 1/2 , if #GA is n^epsilon -enumerable, then GI in P.

  2. Randomized Reductions and Isomorphisms by Jie Wang ( Special Issue on Computational Complexity , results from Dagstuhl-Seminar 1996, Eric Allender editor), 24 February 1999

    Randomizing reductions have provided new techniques for tackling average-case complexity problems. For example, although some NP-complete problems with uniform distributions on instances cannot be complete under deterministic one-one reductions [Wang and Belanger], they are complete under randomized reductions [Venkatesan and Levin]. We study randomized reductions in this paper on reductions that are one-one and honest mappings over certain input domains. These are reasonable assumptions since all the randomized reductions in the literature that are used in proving average-case completeness results possess this property. We consider whether randomized reductions can be inverted efficiently. This gives rise to the issue of randomized isomorphisms. By generalizing the notion of isomorphisms under deterministic reductions, we define what it means for two distributional problems to be isomorphic under randomized reductions. We then show a randomized version of the Cantor-Bernstein-Myhill theorem, which provides a sufficient condition for two distributional problems to be isomorphic under randomized reductions. Based on that condition we show that all the known average-case NP-complete problems (including those that are complete under deterministic reductions) are indeed isomorphic to each other under randomized reductions.

  3. Complements of Multivalued Functions by Stephen Fenner, Frederic Green, Steven Homer, Alan L. Selman, Thomas Thierauf, and Heribert Vollmer, 19 March 1999

    We study the class coNPMV of complements of NPMV functions. Though defined symmetrically to NPMV, this class exhibits very different properties. We clarify the complexity of coNPMV by showing that it is essentially the same as that of NPMV^NP. Complete functions for coNPMV are exhibited and central complexity-theoretic properties of this class are studied. We show that computing maximum satisfying assignments can be done in coNPMV, which leads us to a comparison of NPMV and coNPMV with Krentel's classes MaxP and MinP. The difference hierarchy for NPMV is related to the query hierarchy for coNPMV. Finally, we examine a functional analogue of Chang and Kadin's relationship between a collapse of the Boolean hierarchy over NP and a collapse of the polynomial-time hierarchy.

  4. The Complexity of Generating Test Instances by Christoph Karg, Johannes Köbler, and Rainer Schuler ( Special Issue on Computational Complexity , results from Dagstuhl-Seminar 1996, Eric Allender editor), 22 April 1999

    Recently, Watanabe proposed a framework for testing the correctness and average-case performance of algorithms that purport to solve a given NP search problem efficiently on average with respect to some distribution on the instances. The idea is to randomly generate certified instances under some distribution that resembles the input distribution. Watanabe showed that unless RE=NE , test instances cannot be generated for some NP search problems. We further discuss Watanabe's approach and show, as an upper bound, that test instances can be generated for every \ComplexityClass NP search problem with non-adaptive queries to an NP oracle.

    We also introduce Las Vegas and Monte Carlo types of test instance generators and show that these generators can be used to find out (with high confidence) whether an algorithm is correct and efficient on average. It is shown that Monte Carlo generators can be easily constructed for all RP search problems and that Las Vegas generators exist for all ZPP search problems as well as for other problems such as prime factorization\@. On the other hand, we prove that Monte Carlo generators can only exist for problems in the intersection of NP and coAM .

[] Volume 1998 Abstracts
[back] Volume 1999 [back] Published articles
[CJCTS home]

Last modified: Fri Mar 19 16:06:49 CST 1999