scientific article; zbMATH DE number 1263206

MaRDI QIDQ4234077zbMATH OpenFDO

Authors Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi, Paul Beame, Stephen Cook

Publication date 30 January 2002

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• The relative complexity of NP search problems
• scientific article; zbMATH DE number 1072533
• scientific article; zbMATH DE number 1775419
• Relativizations comparing NP and exponential time
• Towards NP-P via proof complexity and search
• Towards NP-P via proof complexity and search
• NP-completeness: a retrospective
• On the pseudo-deterministic query complexity of NP search problems
• scientific article; zbMATH DE number 847149
• scientific article; zbMATH DE number 1944142

Cited in

(24)

• The relative complexity of NP search problems
• Good degree bounds on Nullstellensatz refutations of the induction principle
• Some graphic uses of an even number of odd nodes
• The complexity of finding a second Hamiltonian cycle in cubic graphs
• On the complexity of the parity argument and other inefficient proofs of existence
• A tight relationship between generic oracles and type-2 complexity theory
• Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
• Inverting onto functions.
• Tractability of cut-free Gentzen-type propositional calculus with permutation inference. II
• Cutting planes, connectivity, and threshold logic
• An exponential separation between the parity principle and the pigeonhole principle
• Structural complexity of multiobjective NP search problems
• On Search Problems in Complexity Theory and in Logic (Abstract)
• scientific article; zbMATH DE number 5527901 (Why is no real title available?)
• The Complexity of Decision Versus Search
• scientific article; zbMATH DE number 1072533 (Why is no real title available?)
• On the polynomial parity argument complexity of the combinatorial Nullstellensatz
• TFNP: an update
• Can PPAD hardness be based on standard cryptographic assumptions?
• Propositional proof complexity
• Feasible interpolation for polynomial calculus and sums-of-squares
• Total NP search problems with abundant solutions
• An oracle with no up-complete sets, but NP = PSPACE
• Which graph motif parameters count?

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4234077)