scientific article; zbMATH DE number 4119625
From MaRDI portal
Publication:4733404
zbMATH Open0683.68039MaRDI QIDQ4733404FDOQ4733404
Authors: Hisao Tanaka 
Publication date: 1989
Title of this publication is not available (Why is that?)
Recommendations
- Strong nondeterministic Turing reduction - a technique for proving intractability
- Strong polynomial-time reducibility
- Nondiamond theorems for polynomial time reducibility
- On Nondeterminism, Enumeration Reducibility and Polynomial Bounds
- On the complexity-relativized strong reducibilities
- Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
- Polynomial time introreducibility
- On relativized nondeterministic polynomial-time bounded computations
- Strong and weak reducibility of algorithmic problems
- scientific article; zbMATH DE number 3963808
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Cited In (11)
- Nontriviality for exponential time w.r.t. weak reducibilities
- A second step toward the strong polynomial-time hierarchy
- Title not available (Why is that?)
- On Nondeterminism, Enumeration Reducibility and Polynomial Bounds
- Title not available (Why is that?)
- Strong nondeterministic Turing reduction - a technique for proving intractability
- Strong extension axioms and Shelah's zero-one law for choiceless polynomial time
- Nontriviality for Exponential Time w.r.t. Weak Reducibilities
- On the power of deterministic reductions to C=P
- Strong co-nondeterministic lower bounds for NP cannot be proved feasibly
- Strong polynomial-time reducibility
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4733404)
