scientific article; zbMATH DE number 4001486

MaRDI QIDQ4727432zbMATH OpenFDO

Authors L. I. Tyagunov

Publication date 1985

zbMATH Keywords

bilinear equationsBoolean formulasconsistencydisjunctive normal formNP-completenesssatisfiability problemsystem of linear or bilinear inequations

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The complexity of satisfiability problems
• scientific article; zbMATH DE number 4039349
• scientific article; zbMATH DE number 1943080
• Satisfiability in Boolean logic (SAT problem) is polynomial
• The solvability of linear systems and the satisfiability

Cited in

(8)

• The solvability of linear systems and the satisfiability
• On the classification of NP-complete problems in terms of their correlation coefficient
• Concerning existential definition of the class NP: Theoretical analysis of an alternative approach
• scientific article; zbMATH DE number 1943080 (Why is no real title available?)
• scientific article; zbMATH DE number 3999295 (Why is no real title available?)
• Satisfiability in Boolean logic (SAT problem) is polynomial
• On the P vs NP question: a proof of inequality
• In some curved spaces, one can solve NP-hard problems in polynomial time

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 Q4727432)