On digital nondeterminism

DOI10.1007/BF01301968zbMath0868.68058MaRDI QIDQ4717055

Felipe Cucker, Martin Matamala

Publication date: 17 August 1997

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

Boolean satisfiability

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Separation of complexity classes in Koiran's weak model ⋮ Computing over the reals with addition and order ⋮ On the complexity of quadratic programming in real number models of computation ⋮ On the P-NP problem over real matrix rings ⋮ On NP-completeness for linear machines ⋮ Dynamical recognizers: real-time language recognition by analog computers ⋮ On NC-real complexity classes for additive circuits and their relations with NC ⋮ Generalization of the subset sum problem and cubic forms ⋮ A note on parallel and alternating time ⋮ The P-DNP problem for infinite Abelian groups ⋮ Exotic quantifiers, complexity classes, and complete problems ⋮ Some aspects of studying an optimization or decision problem in different computational models ⋮ The PCP theorem for NP over the reals ⋮ Computational complexity of multi-player evolutionarily stable strategies ⋮ Logics which capture complexity classes over the reals

Cites Work

• Unnamed Item
• ``Neural computation of decisions in optimization problems
• \(P_ \mathbb{R}{}\neq{}NC_ \mathbb{R}\)
• A note on a \(P \neq NP\) result for a restricted class of real machines
• Two \(P\)-complete problems in the theory of the reals
• Complete problems for deterministic polynomial time
• On the complexity of computations under varying sets of primitives
• Analog computation via neural networks
• Disordered Systems and Biological Organization
• On the Complexity of Quantifier Elimination: the Structural Approach
• Accessible telephone directories
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Bounds for the computational power and learning complexity of analog neural nets
• Neural networks and physical systems with emergent collective computational abilities.