Trading group theory for randomness

Published 1 January 1985

László Babai

Citations772

TL;DR

The aim of this paper is to replace most of the (proven and unproven) group theory of [BS] by elementary combinatorial arguments and defines a new hierarchy of complexity classes “just above NP</italic””, introducing Arthur vs. Merlin games and proving that it consists precisely of those languages which belong to NP.

Abstract

In a previous paper [BS] we proved, using the elements of the theory of nilpotent groups, that some of the fundamental computational problems in matriz groups belong to NP. These problems were also shown to belong to coNP, assuming an unproven hypothesis concerning finite simple groups.

Keywords

Computer ScienceMathematics

Journal of Computer and System SciencesUniversal classes of hash functions

2,573 Citations1979J.Lawrence Carter, Mark N. Wegman

An input independent average linear time algorithm for storage and retrieval on keys that makes a random choice of hash function from a suitable class of hash functions.

The knowledge complexity of interactive proof-systems

1,212 Citations1985Sbafi Goldwasser, Silvio Micali +1 more

View PDF

Journal of Computer and System SciencesRiemann's hypothesis and tests for primality

717 Citations1976Gary L. Miller

SIAM Journal on ComputingComputational Complexity of Probabilistic Turing Machines

694 Citations1977John Gill

It is shown that every nondeterministic machine can be simulated in the same space by a probabilistic machine with small error probability.

SIAM Journal on ComputingA Fast Monte-Carlo Test for Primality

643 Citations1977R. M. Solovay, Volker Strassen

A uniform distribution a from a uniform distribution on the set 1, 2, 3, 4, 5 is a random number and if a and n are relatively prime, compute the residue varepsilon.

A complexity theoretic approach to randomness

469 Citations1983Michael Sipser

A time bounded variant of Kolmogorov complexity is studied, together with universal hashing, which can be used to show that problems solvable probabilistically in polynomial time are all within the second level of the polynometric time hierarchy.

View PDF

SIAM Journal on ComputingRelative to a Random Oracle<i>A</i>, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1

379 Citations1981Charles H. Bennett, John Gill

Let A be a language chosen randomly by tossing a fair coin for each string x to determine whether x belongs to A, and${\bf NP}^A is shown, with probability 1, to contain a-immune set, i.e., a set having no infinite subset in ${\bf P]^A $.

Polynomial-time algorithms for permutation groups

252 Citations1980Merrick L. Furst, John E. Hopcroft +1 more

It is demonstrated that the normal closure of a subgroup can be computed in polynomial time, and that this proceaure can be used to test a group for solvability.

On The Complexity Of Matrix Group Problems I

223 Citations1984László Babai, Endre Szemerédi

A theory of black box groups is built, and it is proved that for such subgroups, membership and divisor of the order are in NPB, and under a plausible mathematical hypothesis on short presentations of finite simple groups, nom membership and exaact order will also be inNPB.

Games against nature

50 Citations1983Christos H. Papadimitriou

A new characterization of PSPACE is proposed, based on some of the most classical and well-looked at problems in Optimization: decision-making under uncertainty, as the class of problems reducible to some polynomial-depth combinatorial two-person game.