On the difference between polynomial-time many-one and truth-table

, , &
Complexity 44:193-219 (1992)
  Copy   BIBTEX

Abstract

This article has no associated abstract. (fix it)

Categories

Add categories

Keywords

Reprint years

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,963

External links

  • This entry has no external links. Add one.
Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Differences between Resource Bounded Degree Structures.Theodore A. Slaman & Michael~E. Mytilinaios - 2003 - Notre Dame Journal of Formal Logic 44 (1):1-12.
Does truth-table of linear norm reduce the one-query tautologies to a random oracle?Masahiro Kumabe, Toshio Suzuki & Takeshi Yamazaki - 2008 - Archive for Mathematical Logic 47 (2):159-180.
On polynomial time computation over unordered structures.Andreas Blass, Yuri Gurevich & Saharon Shelah - 2002 - Journal of Symbolic Logic 67 (3):1093-1125.
Light affine lambda calculus and polynomial time strong normalization.Kazushige Terui - 2007 - Archive for Mathematical Logic 46 (3-4):253-280.
On Nondeterminism, Enumeration Reducibility and Polynomial Bounds.Kate Copestake - 1997 - Mathematical Logic Quarterly 43 (3):287-310.
Polynomial clone reducibility.Quinn Culver - 2014 - Archive for Mathematical Logic 53 (1-2):1-10.
On the structures inside truth-table degrees.Frank Stephan - 2001 - Journal of Symbolic Logic 66 (2):731-770.
Machines Over the Reals and Non‐Uniformity.Felipe Cucker - 1997 - Mathematical Logic Quarterly 43 (2):143-157.
Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices.Klaus Ambos-Spies, Peter A. Fejer, Steffen Lempp & Manuel Lerman - 1996 - Journal of Symbolic Logic 61 (3):880-905.
Polynomial time operations in explicit mathematics.Thomas Strahm - 1997 - Journal of Symbolic Logic 62 (2):575-594.
The Analytic Polynomial-Time Hierarchy.Herbert Baier & Klaus W. Wagner - 1998 - Mathematical Logic Quarterly 44 (4):529-544.
An incomplete set of shortest descriptions.Frank Stephan & Jason Teutsch - 2012 - Journal of Symbolic Logic 77 (1):291-307.
Bounded truth table does not reduce the one-query tautologies to a random oracle.Toshio Suzuki - 2005 - Archive for Mathematical Logic 44 (6):751-762.
Truth-table Schnorr randomness and truth-table reducible randomness.Kenshi Miyabe - 2011 - Mathematical Logic Quarterly 57 (3):323-338.

Analytics

Added to PP
2014-04-05

Downloads
14 (#990,773)

6 months
1 (#1,471,551)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references