Molecular computing, bounded nondeterminism, and efficient recursion

DOI10.1007/3-540-63165-8_234zbMath1401.68075OpenAlexW1921877719MaRDI QIDQ4572009

Richard Beigel, Bin Fu

Publication date: 4 July 2018

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-63165-8_234

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Related Items (1)

The emerging discipline of biomolecular computation in the US

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Solving satisfiability in less than \(2^ n\) steps
• DNA models and algorithms for NP-complete problems
• Classes of bounded nondeterminism
• Algorithms for maximum independent sets
• Natural Self-Reducible Sets
• Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
• Relations Among Complexity Measures
• Nondeterminism within $P^ * $
• Downward Separation Fails Catastrophically for Limited Nondeterminism Classes
• CONSTRUCTING LANGUAGE INSTANCES BASED ON PARTIAL INFORMATION
• On the computational power of DNA

This page was built for publication: Molecular computing, bounded nondeterminism, and efficient recursion