Show simple item record

AuthorKo, Ker-Idc.contributor.author
AuthorOrponen, Pekkadc.contributor.author
AuthorSchöning, Uwedc.contributor.author
AuthorWatanabe, Osamudc.contributor.author
Date of accession2016-03-15T09:03:38Zdc.date.accessioned
Available in OPARU since2016-03-15T09:03:38Zdc.date.available
Year of creation1991dc.date.created
AbstractWe introduce a measure for the computational complexity of individual instances of a decision problern and study some of its properties. The inntance complexity of a string x with respect to a set A and time bound t, ic t(x : A), is defined as the size of the smallest special-case program for A that runs in time t, decides x correctly, and makes no mistakes on other strings ("don´t know" answers are permitted).dc.description.abstract
Languageendc.language.iso
PublisherUniversität Ulmdc.publisher
LicenseStandarddc.rights
Link to license texthttps://oparu.uni-ulm.de/xmlui/license_v3dc.rights.uri
Dewey Decimal GroupDDC 004 / Data processing & computer sciencedc.subject.ddc
LCSHComputational complexitydc.subject.lcsh
TitleInstance complexitydc.title
Resource typeBerichtdc.type
DOIhttp://dx.doi.org/10.18725/OPARU-2426dc.identifier.doi
PPN1651666075dc.identifier.ppn
URNhttp://nbn-resolving.de/urn:nbn:de:bsz:289-vts-81453dc.identifier.urn
GNDKomplexitätsklassedc.subject.gnd
GNDKomplexitätstheoriedc.subject.gnd
FacultyFakultät für Ingenieurwissenschaften und Informatikuulm.affiliationGeneral
Date of activation2012-08-09T11:32:00Zuulm.freischaltungVTS
Peer reviewneinuulm.peerReview
Shelfmark print versionQAA 5/A4.91,1uulm.shelfmark
DCMI TypeTextuulm.typeDCMI
VTS ID8145uulm.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