DocumentCode :
2722068
Title :
On the instance complexity of NP-hard problems
Author :
Orponen, Pekka
Author_Institution :
Dept. of Comput. Sci., Helsinki Univ., Finland
fYear :
1990
fDate :
8-11 July 1990
Firstpage :
20
Lastpage :
27
Abstract :
The t-bounded instance complexity of a string x with respect to a set A, ict(x:A), is defined as the size of the smallest program (roughly, Turing machine) that runs in time t, decides x correctly, and makes no mistakes on other strings (don´t know answers are permitted). For certain conditions on A, it is proved that if P≠NP, then for any polynomial t and constant c, ict(x :A)>c log |x| i.o.; and if EXPTIME≠NEXPTIME, then for any polynomial t there exists a polynomial t´ and a constant c such that ict(x:A)>Kt´(x )-c i.o
Keywords :
computational complexity; EXPTIME≠NEXPTIME; NP-hard problems; P≠NP; Turing machine; decides; instance complexity; polynomial; set; string; Computer science; Polynomials; Turing machines; Upper bound;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Structure in Complexity Theory Conference, 1990, Proceedings., Fifth Annual
Conference_Location :
Barcelona
Print_ISBN :
0-8186-6072-4
Type :
conf
DOI :
10.1109/SCT.1990.113951
Filename :
113951
Link To Document :
https://search.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=2722068
بازگشت