Concepedia

NP search problems in low fragments of bounded arithmetic

Jan Krajı́ček, Alan Skelley, Neil Thapen

Journal of Symbolic Logic · 2007 · 56 citations · 21 references

DOI

Concepts

Abstract

Abstract We give combinatorial and computational characterizations of the NP search problems definable in the bounded arithmetic theories and .

References

21

Optimization, approximation, and complexity classes

Christos H. Papadimitriou, Mihalis Yannakakis · Journal of Computer and System Sciences · 1991 · 1.7K citations

, , +12

On the complexity of the parity argument and other inefficient proofs of existence

Christos H. Papadimitriou · Journal of Computer and System Sciences · 1994 · 797 citations

, , +4

How easy is local search?

David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis · Journal of Computer and System Sciences · 1988 · 714 citations · Full text

, , +8

Exponential lower bounds for the pigeonhole principle

Toniann Pitassi, Paul Beame, Russell Impagliazzo · Computational Complexity · 1993 · 201 citations

, , +9

The Relative Complexity of NP Search Problems

Paul Beame, Stephen Cook, Jeff Edmonds et al. · Journal of Computer and System Sciences · 1998 · 178 citations

, , +14