Positive versions of polynomial time
From MaRDI portal
Publication:1281503
DOI10.1006/inco.1998.2742zbMath0927.68037OpenAlexW2073674197MaRDI QIDQ1281503
Clemens Lautemann, Thomas Schwentick
Publication date: 22 March 1999
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/c048ba3df8482796190a6a035ff4dd07bbfc1706
Related Items (2)
A recursion-theoretic characterisation of the positive polynomial-time functions ⋮ Proof complexity of monotone branching programs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bounds on monotone complexity of the logical permanent
- The method of forced enumeration for nondeterministic automata
- Using the Hamiltonian path operator to capture NP
- An observation on time-storage trade off
- Context-sensitive transitive closure operators
- Monotone separation of logarithmic space from logarithmic depth
- Completeness of path-problems via logical reductions
- Relational queries computable in polynomial time
- Languages that Capture Complexity Classes
- Monotone versus positive
- Nondeterministic Space is Closed under Complementation
- Alternation
- Complete Problems Involving Boolean Labelled Structures and Projection Transactions
- On Relating Time and Space to Size and Depth
- Logical Description of Monotone NP Problems
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
This page was built for publication: Positive versions of polynomial time
