Data Portal @ linkeddatafragments.org

Matches in DBpedia 2014 for { <http://dbpedia.org/resource/P_versus_NP_problem> ?p ?o. }

• P_versus_NP_problem abstract "The P versus NP problem is a major unsolved problem in computer science. Informally, it asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer. It was introduced in 1971 by Stephen Cook in his seminal paper "The complexity of theorem proving procedures" and is considered by many to be the most important open problem in the field. It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute to carry a US$1,000,000 prize for the first correct solution.The informal term quickly used above means the existence of an algorithm for the task that runs in polynomial time. The general class of questions for which some algorithm can provide an answer in polynomial time is called "class P" or just "P". For some questions, there is no known way to find an answer quickly, but if one is provided with information showing what the answer is, it may be possible to verify the answer quickly. The class of questions for which an answer can be verified in polynomial time is called NP.Consider the subset sum problem, an example of a problem that is easy to verify, but whose answer may be difficult to compute. Given a set of integers, does some nonempty subset of them sum to 0? For instance, does a subset of the set {−2, −3, 15, 14, 7, −10} add up to 0? The answer "yes, because {−2, −3, −10, 15} adds up to zero" can be quickly verified with three additions. However, there is no known algorithm to find such a subset in polynomial time (there is one, however, in exponential time, which consists of 2n-1 tries), and indeed such an algorithm can only exist if P = NP; hence this problem is in NP (quickly checkable) but not necessarily in P (quickly solvable).An answer to the P = NP question would determine whether problems that can be verified in polynomial time, like the subset-sum problem, can also be solved in polynomial time. If it turned out that P ≠ NP, it would mean that there are problems in NP (such as NP-complete problems) that are harder to compute than to verify: they could not be solved in polynomial time, but the answer could be verified in polynomial time.Aside from being an important problem in computational theory, a proof either way would have profound implications for mathematics, cryptography, algorithm research, artificial intelligence, game theory, multimedia processing, philosophy, economics and many other fields.".
• P_versus_NP_problem thumbnail Complexity_classes.svg?width=300.
• P_versus_NP_problem wikiPageExternalLink summary?doi=10.1.1.50.4936.
• P_versus_NP_problem wikiPageExternalLink 9937.html.
• P_versus_NP_problem wikiPageExternalLink ?p=122.
• P_versus_NP_problem wikiPageExternalLink weblog.fortnow.com.
• P_versus_NP_problem wikiPageExternalLink millennium.
• P_versus_NP_problem wikiPageExternalLink Official_Problem_Description.pdf.
• P_versus_NP_problem wikiPageExternalLink P-versus-NP.htm.
• P_versus_NP_problem wikiPageExternalLink bc-drafts.html.
• P_versus_NP_problem wikiPageID "6115".
• P_versus_NP_problem wikiPageRevisionID "606718978".
• P_versus_NP_problem hasPhotoCollection P_versus_NP_problem.
• P_versus_NP_problem subject Category:Conjectures.
• P_versus_NP_problem subject Category:Mathematical_optimization.
• P_versus_NP_problem subject Category:Millennium_Prize_Problems.
• P_versus_NP_problem subject Category:Structural_complexity_theory.
• P_versus_NP_problem subject Category:Unsolved_problems_in_computer_science.
• P_versus_NP_problem subject Category:Unsolved_problems_in_mathematics.
• P_versus_NP_problem type Abstraction100002137.
• P_versus_NP_problem type Attribute100024264.
• P_versus_NP_problem type Cognition100023271.
• P_versus_NP_problem type Concept105835747.
• P_versus_NP_problem type Condition113920835.
• P_versus_NP_problem type Conjectures.
• P_versus_NP_problem type Content105809192.
• P_versus_NP_problem type Difficulty114408086.
• P_versus_NP_problem type Hypothesis105888929.
• P_versus_NP_problem type Idea105833840.
• P_versus_NP_problem type MillenniumPrizeProblems.
• P_versus_NP_problem type Problem114410605.
• P_versus_NP_problem type PsychologicalFeature100023100.
• P_versus_NP_problem type Speculation105891783.
• P_versus_NP_problem type State100024720.
• P_versus_NP_problem type UnsolvedProblemsInComputerScience.
• P_versus_NP_problem type UnsolvedProblemsInMathematics.
• P_versus_NP_problem comment "The P versus NP problem is a major unsolved problem in computer science. Informally, it asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer. It was introduced in 1971 by Stephen Cook in his seminal paper "The complexity of theorem proving procedures" and is considered by many to be the most important open problem in the field.".
• P_versus_NP_problem label "Clases de complejidad P y NP".
• P_versus_NP_problem label "Classi di complessità P e NP".
• P_versus_NP_problem label "P versus NP problem".
• P_versus_NP_problem label "P versus NP".
• P_versus_NP_problem label "P-NP-Problem".
• P_versus_NP_problem label "P/NP问题".
• P_versus_NP_problem label "Problème P = NP".
• P_versus_NP_problem label "P≠NP予想".
• P_versus_NP_problem label "Равенство классов P и NP".
• P_versus_NP_problem label "كثير حدود وكثير حدود غير قطعي".
• P_versus_NP_problem sameAs Problém_P_versus_NP.
• P_versus_NP_problem sameAs P-NP-Problem.
• P_versus_NP_problem sameAs Clases_de_complejidad_P_y_NP.
• P_versus_NP_problem sameAs Problème_P_=_NP.
• P_versus_NP_problem sameAs Classi_di_complessità_P_e_NP.
• P_versus_NP_problem sameAs P≠NP予想.
• P_versus_NP_problem sameAs P-NP_문제.
• P_versus_NP_problem sameAs P_versus_NP.
• P_versus_NP_problem sameAs m.01txp.
• P_versus_NP_problem sameAs Q746242.
• P_versus_NP_problem sameAs Q746242.
• P_versus_NP_problem sameAs P_versus_NP_problem.
• P_versus_NP_problem wasDerivedFrom P_versus_NP_problem?oldid=606718978.
• P_versus_NP_problem depiction Complexity_classes.svg.
• P_versus_NP_problem isPrimaryTopicOf P_versus_NP_problem.