Universal resolution for NP-complete problems

DOI10.1016/S0304-3975(97)00029-7MaRDI QIDQ1129008zbMATH OpenFDO

Authors Natacha Portier

Publication date 13 August 1998

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(97)00029-7

zbMATH Keywords

complexityneural networkNP-completenessreduction

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Universal relations and {\#}P-completeness
• On universally easy classes for NP-complete problems.
• On universally easy classes for NP-complete problems
• Universal Relations and #P-Completeness
• Finding a tree structure in a resolution proof is NP-complete

Cites work

• Accessible telephone directories
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 781350 (Why is no real title available?)
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines

Cited in

(6)

• On universally easy classes for NP-complete problems.
• Counting problems over the reals
• On universally easy classes for NP-complete problems
• Universal Relations and #P-Completeness
• All NP-Problems Can Be Solved in Polynomial Time by Accepting Networks of Splicing Processors of Constant Size
• Universal relations and {\#}P-completeness

This page was built for publication: Universal resolution for NP-complete problems

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