Pages that link to "Item:Q5444705"

The following pages link to Consequences of the provability of <i>NP</i> ⊆ <i>P</i>/<i>poly</i> (Q5444705):

Displaying 24 items.

• On an optimal randomized acceptor for graph nonisomorphism (Q413276) (← links)
• Circuit lower bounds in bounded arithmetics (Q466447) (← links)
• Proof systems that take advice (Q553297) (← links)
• On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography (Q693058) (← links)
• AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly (Q1029043) (← links)
• Multifunction algebras and the provability of \(PH\downarrow\) (Q1577486) (← links)
• What one has to know when attacking \(\mathsf {P}\) vs. \(\mathsf {NP}\) (extended abstract) (Q1679951) (← links)
• Competing provers yield improved Karp-Lipton collapse results (Q1775885) (← links)
• Bounding the complexity of advice functions (Q1894454) (← links)
• Feasibly constructive proofs of succinct weak circuit lower bounds (Q2007873) (← links)
• On the amount of nonconstructivity in learning formal languages from text (Q2051759) (← links)
• Polynomial time ultrapowers and the consistency of circuit lower bounds (Q2288334) (← links)
• Induction rules in bounded arithmetic (Q2309507) (← links)
• Unprovability of circuit upper bounds in Cook's theory PV (Q2980966) (← links)
• Do there exist complete sets for promise classes? (Q3107337) (← links)
• Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes (Q3392941) (← links)
• A Tight Karp-Lipton Collapse Result in Bounded Arithmetic (Q3540180) (← links)
• Nondeterministic Instance Complexity and Proof Systems with Advice (Q3618578) (← links)
• On the correspondence between arithmetic theories and propositional proof systems – a survey (Q3619867) (← links)
• Does Advice Help to Prove Propositional Tautologies? (Q3637158) (← links)
• (Q4694254) (← links)
• (Q4779131) (← links)
• INFORMATION IN PROPOSITIONAL PROOFS AND ALGORITHMIC PROOF SEARCH (Q5082067) (← links)
• Automata, Languages and Programming (Q5466529) (← links)