If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances
- Location
-
Deutsche Nationalbibliothek Frankfurt am Main
- ISSN
-
1420-8954
- Extent
-
Online-Ressource
- Language
-
Englisch
- Notes
-
online resource.
- Bibliographic citation
-
If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances ; volume:16 ; number:4 ; day:5 ; month:12 ; year:2007 ; pages:412-441 ; date:12.2007
Computational complexity ; 16, Heft 4 (5.12.2007), 412-441, 12.2007
- Creator
-
Gutfreund, Dan
Shaltiel, Ronen
Ta-Shma, Amnon
- Contributor
-
SpringerLink (Online service)
- DOI
-
10.1007/s00037-007-0235-8
- URN
-
urn:nbn:de:101:1-2021081922021304362947
- Rights
-
Open Access; Der Zugriff auf das Objekt ist unbeschränkt möglich.
- Last update
-
14.08.2025, 11:01 AM CEST
Data provider
This object is provided by:
Deutsche Nationalbibliothek. If you have any questions about the object, please contact the data provider.
Deutsche Nationalbibliothek. If you have any questions about the object, please contact the data provider.
Associated
- Gutfreund, Dan
- Shaltiel, Ronen
- Ta-Shma, Amnon
- SpringerLink (Online service)
Other Objects (12)
Sparse instances of hard problems
Automating Resolution is NP-Hard
Properties of worst-case GMRES
Challenges in implementing worst-case analysis
Pool resolution is NP-hard to recognize
Computing the Interleaving Distance is NP-Hard
Tile-Packing Tomography Is $\mathbbNP}$ -hard
Robust Geometric Programming is co-NP hard
Hard to solve instances of the Euclidean Traveling Salesman Problem
Revisiting Worst-case DEA for Composite Indicators
The worst-case GMRES for normal matrices
Average-case intractability vs. worst-case intractability
Sparse instances of hard problems
Automating Resolution is NP-Hard
Properties of worst-case GMRES
Challenges in implementing worst-case analysis
Pool resolution is NP-hard to recognize
Computing the Interleaving Distance is NP-Hard
Tile-Packing Tomography Is $\mathbbNP}$ -hard
Robust Geometric Programming is co-NP hard
Hard to solve instances of the Euclidean Traveling Salesman Problem
Revisiting Worst-case DEA for Composite Indicators
The worst-case GMRES for normal matrices
Average-case intractability vs. worst-case intractability
Sparse instances of hard problems
Automating Resolution is NP-Hard
Properties of worst-case GMRES
Challenges in implementing worst-case analysis
Pool resolution is NP-hard to recognize
Computing the Interleaving Distance is NP-Hard
Tile-Packing Tomography Is $\mathbbNP}$ -hard
Robust Geometric Programming is co-NP hard
Hard to solve instances of the Euclidean Traveling Salesman Problem
Revisiting Worst-case DEA for Composite Indicators
The worst-case GMRES for normal matrices