Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
From MaRDI portal
Publication:3893305
DOI10.1137/0209003zbMath0447.68044OpenAlexW2021131202MaRDI QIDQ3893305
Patrick C. Fischer, Chandra M. R. Kintala
Publication date: 1980
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0209003
nondeterminismrelativized classesoracle setsclass of languages acceptable by polynomial-time bounded Turing machinesrelativized polynomial-time bounded computations
Related Items (25)
Space-efficient recognition of sparse self-reducible languages ⋮ On problems with short certificates ⋮ Nonlevelable sets and immune sets in the accepting density hierarchy inNP ⋮ Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues] ⋮ The Birth and Early Years of Parameterized Complexity ⋮ IN MEMORIAM CHANDRA KINTALA ⋮ Bounded fixed-parameter tractability and reducibility ⋮ Polynomial-time reducibilities and ``almost all oracle sets ⋮ Relativized alternation and space-bounded computation ⋮ On finding a minimum dominating set in a tournament ⋮ The emptiness problem for intersections of regular languages ⋮ On measuring nondeterminism in regular languages ⋮ Fault-tolerance and complexity (Extended abstract) ⋮ The complexity of manipulative attacks in nearly single-peaked electorates ⋮ On quasilinear-time complexity theory ⋮ On the complexity of monotone dualization and generating minimal hypergraph transversals ⋮ Optimal advice ⋮ On the relation between ambiguity and nondeterminism in finite automata ⋮ Molecular computing, bounded nondeterminism, and efficient recursion ⋮ Measuring nondeterminism in pushdown automata ⋮ Monotone Boolean dualization is in co-NP\([\log^{2}n\).] ⋮ On the space and circuit complexity of parameterized problems: classes and completeness ⋮ Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits ⋮ The minimum equivalent DNF problem and shortest implicants ⋮ Nondeterministics circuits, space complexity and quasigroups
This page was built for publication: Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
