On the power of two-local random reductions

Lance Fortnow; Mario Szegedy

doi:10.1016/0020-0190(92)90104-4

On the power of two-local random reductions

Lance Fortnow, Mario Szegedy

Research output: Contribution to journal › Article › peer-review

5 Scopus citations

Abstract

We show that any language that has a two-locally-random reduction in which the target functions are boolean is in NP{plus 45 degree rule}poly∩co-NP{plus 45 degree rule}poly. This extends and simplifies a result by Yao.

Original language	English (US)
Pages (from-to)	303-306
Number of pages	4
Journal	Information Processing Letters
Volume	44
Issue number	6
DOIs	https://doi.org/10.1016/0020-0190(92)90104-4
State	Published - Dec 28 1992
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Keywords

Computational complexity

Access to Document

10.1016/0020-0190(92)90104-4

Cite this

@article{d9b04dcfb4414bd6ad2c1902ce9d3fcd,

title = "On the power of two-local random reductions",

abstract = "We show that any language that has a two-locally-random reduction in which the target functions are boolean is in NP{plus 45 degree rule}poly∩co-NP{plus 45 degree rule}poly. This extends and simplifies a result by Yao.",

keywords = "Computational complexity",

author = "Lance Fortnow and Mario Szegedy",

note = "Funding Information: “? ? Correspondence to: L. Fortnow, Computer Science Depart-ment, University of Chicago, 1100 E. 58th Street, Chicago, IL 60637b USA. :_! j* Supported in part by NSF Grant CCR-9009936. ” *a, Present address: AT&T Bell Laboratories, 600 Moun-tain Avenue, P.O. Box 636, Murray Hill, NJ 07974, USA.",

year = "1992",

month = dec,

day = "28",

doi = "10.1016/0020-0190(92)90104-4",

language = "English (US)",

volume = "44",

pages = "303--306",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "6",

}

TY - JOUR

T1 - On the power of two-local random reductions

AU - Fortnow, Lance

AU - Szegedy, Mario

N1 - Funding Information: “? ? Correspondence to: L. Fortnow, Computer Science Depart-ment, University of Chicago, 1100 E. 58th Street, Chicago, IL 60637b USA. :_! j* Supported in part by NSF Grant CCR-9009936. ” *a, Present address: AT&T Bell Laboratories, 600 Moun-tain Avenue, P.O. Box 636, Murray Hill, NJ 07974, USA.

PY - 1992/12/28

Y1 - 1992/12/28

N2 - We show that any language that has a two-locally-random reduction in which the target functions are boolean is in NP{plus 45 degree rule}poly∩co-NP{plus 45 degree rule}poly. This extends and simplifies a result by Yao.

AB - We show that any language that has a two-locally-random reduction in which the target functions are boolean is in NP{plus 45 degree rule}poly∩co-NP{plus 45 degree rule}poly. This extends and simplifies a result by Yao.

KW - Computational complexity

UR - http://www.scopus.com/inward/record.url?scp=26444491386&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=26444491386&partnerID=8YFLogxK

U2 - 10.1016/0020-0190(92)90104-4

DO - 10.1016/0020-0190(92)90104-4

M3 - Article

AN - SCOPUS:26444491386

SN - 0020-0190

VL - 44

SP - 303

EP - 306

JO - Information Processing Letters

JF - Information Processing Letters

IS - 6

ER -

On the power of two-local random reductions

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this