loading...
On Heuristic Time Hierarchies
San Diego, California June 13-March 16
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2007.20Twenty-Second Annual IEEE Conference ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Konstantin Pervyshev, "On Heuristic Time Hierarchies," Computational Complexity, Annual IEEE Conference on, pp. 347-358, Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), 2007.
 
 
BibTex
x
 
@article{ 10.1109/CCC.2007.20,
author = {Konstantin Pervyshev},
title = {On Heuristic Time Hierarchies},
journal ={Computational Complexity, Annual IEEE Conference on},
volume = {0},
year = {2007},
issn = {1093-0159},
pages = {347-358},
doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2007.20},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Computational Complexity, Annual IEEE Conference on
TI - On Heuristic Time Hierarchies
SN - 1093-0159
SP347
EP358
A1 - Konstantin Pervyshev,
PY - 2007
KW - null
VL - 0
JA - Computational Complexity, Annual IEEE Conference on
ER -
 
Konstantin Pervyshev, University of California, San Diego, USA
We study the existence of time hierarchies for heuristic algorithms. We prove that a time hierarchy exists for heuristic algorithms in such syntactic classes as NP and co-NP, and also in semantic classes AM and MA. Further, we present an alternative approach to proving time hierarchies for heuristic algorithms in BPP. This leads to a simpler proof than the one known before.
Citation:
Konstantin Pervyshev, "On Heuristic Time Hierarchies," ccc, pp.347-358, Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), 2007
Usage of this product signifies your acceptance of the Terms of Use.