Show simple item record

AuthorSchöning, Uwedc.contributor.author
Date of accession2016-03-14T15:19:55Zdc.date.accessioned
Available in OPARU since2016-03-14T15:19:55Zdc.date.available
Year of creation1992dc.date.created
AbstractWe show that every sparse set S can be many-one reduced to an appropriate tally set T by a polynomial-time, randomized reduction (see formal definitions below). Since T is in NP if S is in NP, this result can be used to show that there is a tally set in NP being randomized many-one complete for all sparse sets in NP. This partially answers an open problem posed by Hartmanis and Yesha [Ha].dc.description.abstract
Languageendc.language.iso
PublisherUniversität Ulmdc.publisher
LicenseStandard (Fassung vom 01.10.2008)dc.rights
Link to license texthttps://oparu.uni-ulm.de/xmlui/license_v2dc.rights.uri
Dewey Decimal GroupDDC 004 / Data processing & computer sciencedc.subject.ddc
LCSHComputational complexitydc.subject.lcsh
TitleOn random reductions from sparse sets to tally setsdc.title
Resource typeArbeitspapierdc.type
DOIhttp://dx.doi.org/10.18725/OPARU-1062dc.identifier.doi
PPN1648289495dc.identifier.ppn
URNhttp://nbn-resolving.de/urn:nbn:de:bsz:289-vts-69645dc.identifier.urn
FacultyFakultät für Ingenieurwissenschaften und Informatikuulm.affiliationGeneral
Date of activation2009-08-09T22:50:01Zuulm.freischaltungVTS
Peer reviewneinuulm.peerReview
Shelfmark print versionQAA 5/A4.92,8uulm.shelfmark
DCMI TypeTextuulm.typeDCMI
VTS ID6964uulm.vtsID
CategoryPublikationenuulm.category
uulm seriesUlmer Informatik-Berichteuulm.seriesUlmName
Bibliographyuulmuulm.bibliographie


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record