scientific article; zbMATH DE number 6482141

MaRDI QIDQ2945856zbMATH OpenFDO

Authors Olga Kosheleva, Vladik Kreinovich

Publication date 14 September 2015

Full work available at URL http://msm.univer.omsk.su/jrn29/tr13-34a.pdf

zbMATH Keywords

computation in curved space-timeNP-hard problemspace-time model

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Time-space tradeoffs for satisfiability
• Time-space lower bounds for satisfiability
• Time-space lower bounds for satisfiability
• Space complexity in propositional calculus
• Space Complexity in Propositional Calculus
• scientific article; zbMATH DE number 2156275
• Space-time isomorphism problem is intractable (NP-hard)
• Complete problems for space bounded subclasses of NP
• Time-space tradeoffs for SAT on nonuniform machines
• Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal Logic

Cited in

(4)

• If many physicists are right and no physical theory is perfect, then by using physical observations, we can feasibly solve almost all instances of each NP-complete problem
• Unbounded hardware is equivalent to deterministic Turing machines
• Space-time isomorphism problem is intractable (NP-hard)
• 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 Q2945856)