Matches in DBpedia 2015-10 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 essentially first mentioned in a 1956 letter written by Kurt Gödel to John von Neumann. Gödel asked whether a certain NP-complete problem could be solved in quadratic or linear time. The precise statement of the P versus NP problem 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 is 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 the subset {−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-n-1 tries), but such an algorithm exists 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 weblog.fortnow.com.
- P_versus_NP_problem wikiPageExternalLink fulltext.
- 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 millennium-problems.
- P_versus_NP_problem wikiPageExternalLink pvsnp.pdf.
- P_versus_NP_problem wikiPageExternalLink FraenkelL81.
- 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 wikiPageLength "53834".
- P_versus_NP_problem wikiPageOutDegree "162".
- P_versus_NP_problem wikiPageRevisionID "682785407".
- P_versus_NP_problem wikiPageWikiLink Advanced_Encryption_Standard.
- P_versus_NP_problem wikiPageWikiLink Alexander_Razborov.
- P_versus_NP_problem wikiPageWikiLink Algorithm.
- P_versus_NP_problem wikiPageWikiLink Anil_Nerode.
- P_versus_NP_problem wikiPageWikiLink Artificial_intelligence.
- P_versus_NP_problem wikiPageWikiLink Average-case_complexity.
- P_versus_NP_problem wikiPageWikiLink Avi_Wigderson.
- P_versus_NP_problem wikiPageWikiLink Big_O_notation.
- P_versus_NP_problem wikiPageWikiLink Boolean_satisfiability_problem.
- P_versus_NP_problem wikiPageWikiLink Category:Conjectures.
- P_versus_NP_problem wikiPageWikiLink Category:Mathematical_optimization.
- P_versus_NP_problem wikiPageWikiLink Category:Millennium_Prize_Problems.
- P_versus_NP_problem wikiPageWikiLink Category:Structural_complexity_theory.
- P_versus_NP_problem wikiPageWikiLink Category:Unsolved_problems_in_computer_science.
- P_versus_NP_problem wikiPageWikiLink Category:Unsolved_problems_in_mathematics.
- P_versus_NP_problem wikiPageWikiLink Certificate_(complexity).
- P_versus_NP_problem wikiPageWikiLink Clay_Math_Institute.
- P_versus_NP_problem wikiPageWikiLink Clay_Mathematics_Institute.
- P_versus_NP_problem wikiPageWikiLink Co-NP.
- P_versus_NP_problem wikiPageWikiLink Cobhams_thesis.
- P_versus_NP_problem wikiPageWikiLink Complexity_class.
- P_versus_NP_problem wikiPageWikiLink Composite_number.
- P_versus_NP_problem wikiPageWikiLink Computational_complexity_theory.
- P_versus_NP_problem wikiPageWikiLink Computer_programming.
- P_versus_NP_problem wikiPageWikiLink Constructive_proof.
- P_versus_NP_problem wikiPageWikiLink Cook–Levin_theorem.
- P_versus_NP_problem wikiPageWikiLink Cornell_University.
- P_versus_NP_problem wikiPageWikiLink Decision_problem.
- P_versus_NP_problem wikiPageWikiLink Descriptive_complexity.
- P_versus_NP_problem wikiPageWikiLink Descriptive_complexity_theory.
- P_versus_NP_problem wikiPageWikiLink Deterministic_automaton.
- P_versus_NP_problem wikiPageWikiLink Deterministic_computation.
- P_versus_NP_problem wikiPageWikiLink Discrete_logarithm.
- P_versus_NP_problem wikiPageWikiLink Discrete_logarithm_problem.
- P_versus_NP_problem wikiPageWikiLink Donald_Knuth.
- P_versus_NP_problem wikiPageWikiLink EXPTIME.
- P_versus_NP_problem wikiPageWikiLink Economics.
- P_versus_NP_problem wikiPageWikiLink Elementary_(TV_series).
- P_versus_NP_problem wikiPageWikiLink Entscheidungsproblem.
- P_versus_NP_problem wikiPageWikiLink Eugene_Luks.
- P_versus_NP_problem wikiPageWikiLink Eugene_M._Luks.
- P_versus_NP_problem wikiPageWikiLink Exponential_time.
- P_versus_NP_problem wikiPageWikiLink Fermats_Last_Theorem.
- P_versus_NP_problem wikiPageWikiLink First-order_logic.
- P_versus_NP_problem wikiPageWikiLink Fixed-point_combinator.
- P_versus_NP_problem wikiPageWikiLink Game_complexity.
- P_versus_NP_problem wikiPageWikiLink Game_theory.
- P_versus_NP_problem wikiPageWikiLink General_number_field_sieve.
- P_versus_NP_problem wikiPageWikiLink Gerhard_J._Woeginger.
- P_versus_NP_problem wikiPageWikiLink Graph_(mathematics).
- P_versus_NP_problem wikiPageWikiLink Graph_isomorphism.
- P_versus_NP_problem wikiPageWikiLink Graph_isomorphism_problem.
- P_versus_NP_problem wikiPageWikiLink HP_Labs.
- P_versus_NP_problem wikiPageWikiLink Halting_problem.
- P_versus_NP_problem wikiPageWikiLink Hash_function.
- P_versus_NP_problem wikiPageWikiLink IP_(complexity).
- P_versus_NP_problem wikiPageWikiLink Independence_(mathematical_logic).
- P_versus_NP_problem wikiPageWikiLink Independent_(mathematical_logic).
- P_versus_NP_problem wikiPageWikiLink Information-theoretic_security.
- P_versus_NP_problem wikiPageWikiLink Integer.
- P_versus_NP_problem wikiPageWikiLink Integer_factorization.
- P_versus_NP_problem wikiPageWikiLink Integer_factorization_problem.
- P_versus_NP_problem wikiPageWikiLink Integer_programming.
- P_versus_NP_problem wikiPageWikiLink Introduction_to_Algorithms.
- P_versus_NP_problem wikiPageWikiLink John_von_Neumann.
- P_versus_NP_problem wikiPageWikiLink Karps_21_NP-complete_problems.
- P_versus_NP_problem wikiPageWikiLink Knapsack_problem.
- P_versus_NP_problem wikiPageWikiLink Kurt_Gödel.
- P_versus_NP_problem wikiPageWikiLink Laszlo_Babai.
- P_versus_NP_problem wikiPageWikiLink Leonid_Levin.
- P_versus_NP_problem wikiPageWikiLink Linear_order.
- P_versus_NP_problem wikiPageWikiLink Linear_programming.
- P_versus_NP_problem wikiPageWikiLink List_of_NP-complete_problems.
- P_versus_NP_problem wikiPageWikiLink List_of_unsolved_problems_in_computer_science.
- P_versus_NP_problem wikiPageWikiLink List_of_unsolved_problems_in_mathematics.
- P_versus_NP_problem wikiPageWikiLink László_Babai.
- P_versus_NP_problem wikiPageWikiLink MIT.
- P_versus_NP_problem wikiPageWikiLink MIT_Press.
- P_versus_NP_problem wikiPageWikiLink Massachusetts_Institute_of_Technology.
- P_versus_NP_problem wikiPageWikiLink Michael_O._Rabin.
- P_versus_NP_problem wikiPageWikiLink Millennium_Prize_Problems.
- P_versus_NP_problem wikiPageWikiLink Moshe_Vardi.
- P_versus_NP_problem wikiPageWikiLink Moshe_Y._Vardi.
- P_versus_NP_problem wikiPageWikiLink NP-complete.