Propositional proofs and reductions between NP search problems
type: Item
instance of: scholarly article
title: Propositional proofs and reductions between NP search problems
zbMATH Open document ID: 1252.03127
author: Samuel R. Buss
author: Alan S. Johnson
published in: Annals of Pure and Applied Logic
publication date: 2012-07-11T00:00:00Z
Mathematics Subject Classification ID: 03F07
Mathematics Subject Classification ID: 03B05
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03D30
Mathematics Subject Classification ID: 03F20
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 6054355
zbMATH Keywords: search problems
zbMATH Keywords: Nullstellensatz
zbMATH Keywords: propositional proofs
zbMATH Keywords: polynomial-time reducibility
MaRDI profile type: Publication
full work available at URL: j.apal.2012.01.015
OpenAlex ID: W2065828765
cites work: The relative complexity of NP search problems
cites work: Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
cites work: An exponential separation between the parity principle and the pigeonhole principle
cites work: Separation results for the size of constant-depth propositional proofs
cites work: Corrected upper bounds for free-cut elimination
cites work: Q4375786
cites work: Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
cites work: An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
cites work: Q4228469
cites work: A tight relationship between generic oracles and type-2 complexity theory
cites work: The complexity of computing a Nash equilibrium
cites work: Herbrandizing search problems in Bounded Arithmetic
cites work: How easy is local search?
cites work: Q4856172
cites work: On total functions, existence theorems and computational complexity
cites work: On the complexity of the parity argument and other inefficient proofs of existence
DOI: 10.1016/J.APAL.2012.01.015
description: scientific article; zbMATH DE number 6054355