Add to ORKGA basic question about NP is whether or not search reduces in polynomial time to decision. We indicate that the answer is negative: under a complexity assumption (that deterministic and non-deterministic double-exponential time are unequal) we construct a language in NP for which search does not reduce to decision. These ideas extend in a natural way to interactive proofs and program checking. Under similar assumptions we present languages in NP for which it is harder to prove membership interactively than it is to decide this membership, and languages in NP which are not checkable. Keywords: NP-completeness, self-reducibility, interactive proofs, program checking, sparse sets, quadratic residuosity. Department of Computer Science & E...
AbstractWe distinguish self-reducibility of a languageLwith the question of whether search reduces t...
P versus NP is considered as one of the most important open problems in computer science. This consi...
We distinguish self-reducibility of a language L with the question of whether search reduces to deci...
Under the hypothesis that NP does not have p-measure 0 (roughly, that NP contains more than a neglig...
Under the hypothesis that NP does not have p-measure 0 (roughly, that NP contains more than a neglig...
AbstractUnder the hypothesis that NP does not have p-measure 0 (roughly, that NP contains more than ...
Under the hypothesis that NP does not have p-measure 0 (roughly, that NP contains more than a neglig...
This is a survey of work on proof complexity and proof search from a logico-algorithmic viewpoint, a...
Under the hypothesis that NP does not have p-measure O (roughly, that NP contains more than a negli...
Papadimitriou introduced several classes of NP search prob-lemsbased on combinatorial principles whi...
Introduction One of the important questions in computational complexity theory is whether every NP ...
Subproblems have become an important object of NP-completeness theory since its beginning. In this p...
AbstractUnder the assumption that NP does not have p-measure 0, we investigate reductions to NP-comp...
A set is P-selective [Sel79] if there is a polynomial-time semi-decision algorithm for the set---an ...
AbstractThis is a survey of work on proof complexity and proof search from a logico-algorithmic view...
AbstractWe distinguish self-reducibility of a languageLwith the question of whether search reduces t...
P versus NP is considered as one of the most important open problems in computer science. This consi...
We distinguish self-reducibility of a language L with the question of whether search reduces to deci...
Under the hypothesis that NP does not have p-measure 0 (roughly, that NP contains more than a neglig...
Under the hypothesis that NP does not have p-measure 0 (roughly, that NP contains more than a neglig...
AbstractUnder the hypothesis that NP does not have p-measure 0 (roughly, that NP contains more than ...
Under the hypothesis that NP does not have p-measure 0 (roughly, that NP contains more than a neglig...
This is a survey of work on proof complexity and proof search from a logico-algorithmic viewpoint, a...
Under the hypothesis that NP does not have p-measure O (roughly, that NP contains more than a negli...
Papadimitriou introduced several classes of NP search prob-lemsbased on combinatorial principles whi...
Introduction One of the important questions in computational complexity theory is whether every NP ...
Subproblems have become an important object of NP-completeness theory since its beginning. In this p...
AbstractUnder the assumption that NP does not have p-measure 0, we investigate reductions to NP-comp...
A set is P-selective [Sel79] if there is a polynomial-time semi-decision algorithm for the set---an ...
AbstractThis is a survey of work on proof complexity and proof search from a logico-algorithmic view...
AbstractWe distinguish self-reducibility of a languageLwith the question of whether search reduces t...
P versus NP is considered as one of the most important open problems in computer science. This consi...
We distinguish self-reducibility of a language L with the question of whether search reduces to deci...