About: P, NP, and NP-completeness, the basics of computational complexity

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: P, NP, and NP-completeness, the basics of computational complexity Goto Sponge NotDistinct Permalink

An Entity of Type : rdac:C10001, within Data Space : data.idref.fr associated with source document(s)

Attributes	Values
type	frbr:Work rdac:C10001
Author	Goldreich, Oded (1957-....)
dc:subject	Computational complexity Algorithmes Approximation theory Approximation, Théorie de l' Polynômes Complexité de calcul (informatique) Polynomials Computer algorithms
preferred label	P, NP, and NP-completeness, the basics of computational complexity
Language	http://lexvo.org/id/iso639-3/eng
Subject	http://www.idref.fr/027551261/id http://www.idref.fr/027829227/id http://www.idref.fr/027282171/id http://www.idref.fr/027282716/id
dc:title	P, NP, and NP-completeness, the basics of computational complexity
note	La quatrième de couv. porte : \"The focus of this book is the P-versus-NP Question and the theory of NP-completeness. It also provides adequate preliminaries regarding computational problems and computational models. The P versus NP Question asks whether or not finding solutions is harder than checking the correctness of solutions. An alternative formulation asks whether or not discovering proofs is harder than verifying their correctness. It is widely believed that the answer to these equivalent formulations is positive, and this is captured by saying that P is different from NP. Although the P-versus-NP Question remains unresolved, the theory of NP-completeness offers evidence for the intractability of specific problems in NP by showing that they are universal for the entire class. Amazingly enough, NP-complete problems exist, and hundreds of natural computational problems arising in many different areas of mathematics and science are NP-complete\"
dc:type	Text
http://iflastandar...bd/elements/P1001	http://iflastandards.info/ns/isbd/terms/contentform/T1009
rdaw:P10219	2010
has content type	http://rdaregistry.info/termList/RDAContentType/1020
is primary topic of	http://www.idref.fr/218717547
is rdam:P30135 of	http://www.sudoc.fr/152242414/id http://www.sudoc.fr/156520400/id

Faceted Search & Find service v1.13.91 as of Aug 16 2018

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3229 as of May 14 2019, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (70 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software