In some curved spaces, one can solve NP-hard problems in polynomial time

DOI10.1007/s10958-009-9402-6zbMath1178.68662OpenAlexW2093392279MaRDI QIDQ843612

Vladik Ya. Kreinovich, Maurice Margenstern

Publication date: 15 January 2010

Published in: Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

Full work available at URL: https://digitalcommons.utep.edu/cgi/viewcontent.cgi?article=1151&context=cs_techrep

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Related Items (2)

Is the World Itself Fuzzy? Physical Arguments and Unexpected Computational Consequences of Zadeh’s Vision ⋮ INDUCTIVE COMPLEXITY OF THE P VERSUS NP PROBLEM

Cites Work

• A universal cellular automaton in the hyperbolic plane.
• On Gurevich's theorem on sequential algorithms
• Theoretical and experimental DNA computation.
• Eliminating duplicates under interval and fuzzy uncertainty: an asymptotically optimal algorithm and its geospatial applications
• Abstract State Machines
• Evolving Algebras 1993: Lipari Guide
• Cellular Automata in the Hyperbolic Plane: Proposal for a New Environment
• Simple self-reproducing universal automata
• Sequential abstract-state machines capture sequential algorithms
• NP problems are tractable in the space of cellular automata in the hyperbolic plane
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: In some curved spaces, one can solve NP-hard problems in polynomial time