Show simple item record

dc.contributor.authorHartmanis, Jurisen_US
dc.contributor.authorHemachandra, Lane A.en_US
dc.date.accessioned2007-04-23T17:13:53Z
dc.date.available2007-04-23T17:13:53Z
dc.date.issued1986-04en_US
dc.identifier.citationhttp://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR86-746en_US
dc.identifier.urihttps://hdl.handle.net/1813/6586
dc.description.abstractThis paper develops techniques for studying complexity classes that are not covered by known recursive enumerations of machines. Often, counting classes, probabilistic classes, and intersection classes lack such enumerations. Concentrating on the counting class UP, we show that there are relativizations for which $UP^{A}$ has no complete languages and other relativizations for which $P^{B} \neq UP^{B} \neq NP^{B}$ and $UP^{B}$ has complete languages. Among other results we show that $P \neq UP$ if and only if there exists a set $S$ in $P$ of Boolean formulas with at most one satisfying assignment such that $S \bigcap SAT$ is not in $P$. $P \neq UP \bigcap coUP$ if and only if there exists a set $S$ in $P$ of uniquely satisfiable Boolean formulas such that no polynomial-time machine can compute the solutions for the formulas in $S$. If $UP$ has complete languages then there exists a set $R$ in $P$ of Boolean formulas with at most one satisfying assignment so that $SAT \bigcap R$ is complete for $UP$. Finally, we indicate the wide applicability of our techniques to counting and probabilistic classes by using them to examine the probabilistic class $BPP$. There is a relativized world where $BPP^{A}$ has no complete languages. If $BPP$ has complete languages then it has a complete language of the form $B \bigcap MAJORITY$, where $B \in P$ and $MAJORITY = \{f | f$ is true for at least half of all assignments\} is the canonical $PP$-complete set.en_US
dc.format.extent1569350 bytes
dc.format.extent333373 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypeapplication/postscript
dc.language.isoen_USen_US
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleComplexity Classes Without Machines: On Complete Languages for UPen_US
dc.typetechnical reporten_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

Statistics