A Note on Non-complete Problems in NP[formula omitted]

This note deals with the structure of the class NPR introduced by L. Blum, M. Shub, and S. Smale (1989, Bull. Amer. Math. Soc.21, 1–46). It is shown that, assuming NPR⊈PR/poly, there exists a problem NPR\(PR/poly) which is not NPR-complete (w.r.t PR/poly reductions). It also clarifies the scope of a...

Full description

Saved in:
Bibliographic Details
Published in:Journal of Complexity 2000-03, Vol.16 (1), p.324-332
Main Authors: Ben-David, S., Meer, K., Michaux, C.
Format: Article
Language:English
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page 332
container_issue 1
container_start_page 324
container_title Journal of Complexity
container_volume 16
creator Ben-David, S.
Meer, K.
Michaux, C.
description This note deals with the structure of the class NPR introduced by L. Blum, M. Shub, and S. Smale (1989, Bull. Amer. Math. Soc.21, 1–46). It is shown that, assuming NPR⊈PR/poly, there exists a problem NPR\(PR/poly) which is not NPR-complete (w.r.t PR/poly reductions). It also clarifies the scope of a padding technique used in a former similar result by R. Ladner (1975, J. Assoc. Comput. Mach.22, 155–171) concerning the structure of the class NP (in the common, Turing machine, model).
doi_str_mv 10.1006/jcom.1999.0537
format article
fullrecord <record><control><sourceid>elsevier</sourceid><recordid>TN_cdi_elsevier_sciencedirect_doi_10_1006_jcom_1999_0537</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S0885064X9990537X</els_id><sourcerecordid>S0885064X9990537X</sourcerecordid><originalsourceid>FETCH-elsevier_sciencedirect_doi_10_1006_jcom_1999_05373</originalsourceid><addsrcrecordid>eNqljssKwjAURIMoWB9b1_mB1BtrY7sUUVxJFy4EkVDbW0hJGmmq328C_oGr4TDMcAhZcYg5gFi3lTUxz_M8hjTZjUjEIQe22UE2JhFkWcpAbG9TMnOuBeA8FTwiYk8vdkBqO58d8xcvjZ6L3j41GkeVL4p7Y3vz1iW1Rg0D1o8FmTSldrj85Zxkp-P1cGbo4aOwl65S2FVYqx6rQdZWSQ4yeMrgKYOnDJ7JH9Mv1G5KHg</addsrcrecordid><sourcetype>Publisher</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>A Note on Non-complete Problems in NP[formula omitted]</title><source>ScienceDirect Journals</source><creator>Ben-David, S. ; Meer, K. ; Michaux, C.</creator><creatorcontrib>Ben-David, S. ; Meer, K. ; Michaux, C.</creatorcontrib><description>This note deals with the structure of the class NPR introduced by L. Blum, M. Shub, and S. Smale (1989, Bull. Amer. Math. Soc.21, 1–46). It is shown that, assuming NPR⊈PR/poly, there exists a problem NPR\(PR/poly) which is not NPR-complete (w.r.t PR/poly reductions). It also clarifies the scope of a padding technique used in a former similar result by R. Ladner (1975, J. Assoc. Comput. Mach.22, 155–171) concerning the structure of the class NP (in the common, Turing machine, model).</description><identifier>ISSN: 0885-064X</identifier><identifier>EISSN: 1090-2708</identifier><identifier>DOI: 10.1006/jcom.1999.0537</identifier><language>eng</language><publisher>Elsevier Inc</publisher><ispartof>Journal of Complexity, 2000-03, Vol.16 (1), p.324-332</ispartof><rights>2000 Academic Press</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Ben-David, S.</creatorcontrib><creatorcontrib>Meer, K.</creatorcontrib><creatorcontrib>Michaux, C.</creatorcontrib><title>A Note on Non-complete Problems in NP[formula omitted]</title><title>Journal of Complexity</title><description>This note deals with the structure of the class NPR introduced by L. Blum, M. Shub, and S. Smale (1989, Bull. Amer. Math. Soc.21, 1–46). It is shown that, assuming NPR⊈PR/poly, there exists a problem NPR\(PR/poly) which is not NPR-complete (w.r.t PR/poly reductions). It also clarifies the scope of a padding technique used in a former similar result by R. Ladner (1975, J. Assoc. Comput. Mach.22, 155–171) concerning the structure of the class NP (in the common, Turing machine, model).</description><issn>0885-064X</issn><issn>1090-2708</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2000</creationdate><recordtype>article</recordtype><recordid>eNqljssKwjAURIMoWB9b1_mB1BtrY7sUUVxJFy4EkVDbW0hJGmmq328C_oGr4TDMcAhZcYg5gFi3lTUxz_M8hjTZjUjEIQe22UE2JhFkWcpAbG9TMnOuBeA8FTwiYk8vdkBqO58d8xcvjZ6L3j41GkeVL4p7Y3vz1iW1Rg0D1o8FmTSldrj85Zxkp-P1cGbo4aOwl65S2FVYqx6rQdZWSQ4yeMrgKYOnDJ7JH9Mv1G5KHg</recordid><startdate>200003</startdate><enddate>200003</enddate><creator>Ben-David, S.</creator><creator>Meer, K.</creator><creator>Michaux, C.</creator><general>Elsevier Inc</general><scope>6I.</scope><scope>AAFTH</scope></search><sort><creationdate>200003</creationdate><title>A Note on Non-complete Problems in NP[formula omitted]</title><author>Ben-David, S. ; Meer, K. ; Michaux, C.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-elsevier_sciencedirect_doi_10_1006_jcom_1999_05373</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2000</creationdate><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Ben-David, S.</creatorcontrib><creatorcontrib>Meer, K.</creatorcontrib><creatorcontrib>Michaux, C.</creatorcontrib><collection>ScienceDirect Open Access Titles</collection><collection>Elsevier:ScienceDirect:Open Access</collection><jtitle>Journal of Complexity</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Ben-David, S.</au><au>Meer, K.</au><au>Michaux, C.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>A Note on Non-complete Problems in NP[formula omitted]</atitle><jtitle>Journal of Complexity</jtitle><date>2000-03</date><risdate>2000</risdate><volume>16</volume><issue>1</issue><spage>324</spage><epage>332</epage><pages>324-332</pages><issn>0885-064X</issn><eissn>1090-2708</eissn><abstract>This note deals with the structure of the class NPR introduced by L. Blum, M. Shub, and S. Smale (1989, Bull. Amer. Math. Soc.21, 1–46). It is shown that, assuming NPR⊈PR/poly, there exists a problem NPR\(PR/poly) which is not NPR-complete (w.r.t PR/poly reductions). It also clarifies the scope of a padding technique used in a former similar result by R. Ladner (1975, J. Assoc. Comput. Mach.22, 155–171) concerning the structure of the class NP (in the common, Turing machine, model).</abstract><pub>Elsevier Inc</pub><doi>10.1006/jcom.1999.0537</doi><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 0885-064X
ispartof Journal of Complexity, 2000-03, Vol.16 (1), p.324-332
issn 0885-064X
1090-2708
language eng
recordid cdi_elsevier_sciencedirect_doi_10_1006_jcom_1999_0537
source ScienceDirect Journals
title A Note on Non-complete Problems in NP[formula omitted]
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-29T11%3A52%3A27IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-elsevier&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=A%20Note%20on%20Non-complete%20Problems%20in%20NP%5Bformula%20omitted%5D&rft.jtitle=Journal%20of%20Complexity&rft.au=Ben-David,%20S.&rft.date=2000-03&rft.volume=16&rft.issue=1&rft.spage=324&rft.epage=332&rft.pages=324-332&rft.issn=0885-064X&rft.eissn=1090-2708&rft_id=info:doi/10.1006/jcom.1999.0537&rft_dat=%3Celsevier%3ES0885064X9990537X%3C/elsevier%3E%3Cgrp_id%3Ecdi_FETCH-elsevier_sciencedirect_doi_10_1006_jcom_1999_05373%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rfr_iscdi=true