Show simple item record

dc.contributor.authorHemachandra, Lane A.en_US
dc.date.accessioned2007-04-23T17:21:02Z
dc.date.available2007-04-23T17:21:02Z
dc.date.issued1987-07en_US
dc.identifier.citationhttp://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR87-852en_US
dc.identifier.urihttps://hdl.handle.net/1813/6692
dc.description.abstractThe class of near-testable sets, NT, was defined by Goldsmith, Joseph, and Young. They noted that $P \subseteq NT \subseteq PSPACE$, and asked whether P=NT. This note shows that NT shares the same $m$-degree as the parity-based complexity class $\bigoplus P$ (i.e., $NT\equiv^{p}_{m} \oplus P$) and uses this to prove that relative to a random oracle $A, P^{A} \neq NT^{A}$ with probability one. Indeed, with probability one, $NT^{A} - (NP^{A} \bigcup coNP^{A}) \neq 0$.en_US
dc.format.extent738466 bytes
dc.format.extent199689 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.titleOn Parity and Near-Testability: $P^{A} \neq NT^{A}$ With Probability 1en_US
dc.typetechnical reporten_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

Statistics