About: P versus NP problem

Property	Value
dbo:description	problema matematico (it) matematikai probléma (hu) problème mathématique (fr) la problemo en informadiko pri ĉu la komplikoklaso P, kiu estas subklaso de la komplikoklaso NP, fakte egalas NP (eo) Одна из главных не решённых проблем теории алгоритмов (ru) unsolved problem in computer science about time complexity (en) problem inom datavetenskap (sv) problema aberto em ciência da computação (pt) problém teoretické informatiky (cs) ratkaisematon ongelma tietojenkäsittelytieteessä (fi) problema d'infromàtica no resolt sobre la complexitat computacional (ca) ungelöstes Problem der Mathematik und theoretischen Informatik (de) нерешен проблем у рачунарству о временској сложености (sr) P=NP-ի ապացուցումը համակարգչային բարդագույն ծառացած խնդիրներից է (hy) 計算機科學中有關時間複雜性的未解決問題 (zh) masalah yang belum terpecahkan dalam sains komputer (in) בעיה במדעי המחשב (iw) 数学の未解決問題 (ja)
dbo:thumbnail	wiki-commons:Special:FilePath/P_np_np-complete_np-hard.svg?width=300
dbo:wikiPageExternalLink	https://awards.acm.org/about/2017-doctoral-dissertation https://www2.eecs.berkeley.edu/Pubs/TechRpts/2017/EECS-2017-146.pdf https://www.claymath.org/millennium-problems/p-vs-np-problem http://weblog.fortnow.com https://www.youtube.com/watch%3Fv=YX40hbAHx3s https://www.britannica.com/science/P-versus-NP-problem https://ghostarchive.org/varchive/youtube/20211124/YX40hbAHx3s%7C http://www.wisdom.weizmann.ac.il/~oded/bc-drafts.html https://www.scientificamerican.com/article/the-top-unsolved-questions-in-mathematics-remain-mostly-mysterious/ https://archive.org/details/computersintract0000gare
dbo:wikiPageWikiLink	dbr:ZFC dbr:Fermat's_Last_Theorem dbr:MIT_Press dbr:Peano_axioms dbr:Co-NP dbr:Presburger_arithmetic dbr:Chess dbr:Encyclopædia_Britannica dbr:The_Simpsons dbr:YouTube dbr:Cryptographic_hash_function dbr:General_number_field_sieve dbr:Travelling_Salesman_(2012_film) dbr:Gerhard_J._Woeginger dbr:Subset_sum_problem dbc:Structural_complexity_theory dbr:Algorithm dbr:Artificial_intelligence dbr:Association_for_Computing_Machinery dbr:Avi_Wigderson dbr:Computer_science dbr:Cornell_University dbr:Cryptography dbr:Donald_Knuth dbr:Economics dbr:Philosophy dbr:Rice_University dbr:Theoretical_computer_science dbr:Turing_machine dbr:Bitcoin dbr:John_Forbes_Nash_Jr. dbr:Simplex_algorithm dbr:Triple_DES dbc:Unsolved_problems_in_mathematics dbc:Unsolved_problems_in_computer_science dbc:Millennium_Prize_Problems dbr:Anil_Nerode dbr:Game_theory dbr:PSPACE dbr:Computational_complexity_theory dbr:John_von_Neumann dbr:László_Babai dbr:Michael_J._Fischer dbr:National_Security_Agency dbr:Princeton_University dbr:Richard_E._Ladner dbr:Composite_number dbr:Latin_square dbr:Elementary_(TV_series) dbr:Boolean_satisfiability_problem dbr:Knapsack_problem dbr:Universal_quantification dbr:Robert_M._Solovay dbr:Decision_problem dbr:Quantum_complexity_theory dbr:IP_(complexity) dbr:Millennium_Prize_Problems dbr:Complexity_class dbr:Graph_minor dbr:Independence_(mathematical_logic) dbr:Halting_problem dbr:List_of_Elementary_episodes dbr:Blockchain dbr:Computer_programming dbr:Kurt_Gödel dbr:Polynomial dbr:Sudoku dbr:Clay_Mathematics_Institute dbr:Graph_(discrete_mathematics) dbr:Big_O_notation dbr:String_(computer_science) dbr:Shor's_algorithm dbr:W._H._Freeman_and_Company dbr:Certificate_(complexity) dbr:Fixed-point_combinator dbr:Linear_programming dbr:AKS_primality_test dbr:Alexander_Razborov dbr:Average-case_complexity dbr:Cobham's_thesis dbr:Entscheidungsproblem dbr:Integer_programming dbr:Karp's_21_NP-complete_problems dbr:Leonid_Levin dbr:Michael_O._Rabin dbr:NP_(complexity) dbr:Russell_Impagliazzo dbr:Scott_Aaronson dbr:Steven_Rudich dbr:Protein_structure_prediction dbr:Polynomial_hierarchy dbr:Cook–Levin_theorem dbr:First-order_logic dbr:Second-order_logic dbr:Stephen_Cook dbr:Advanced_Encryption_Standard dbr:Operations_research dbr:PH_(complexity) dbr:Natural_proof dbr:Public-key_cryptography dbr:Randomized_algorithm dbr:Algorithmic_efficiency dbr:Quantum_algorithm dbr:Travelling_salesman_problem dbr:List_of_unsolved_problems_in_mathematics dbr:P_(complexity) dbr:Theory_of_computation dbr:Time_complexity dbr:Treehouse_of_Horror_VI dbr:Signature_(logic) dbr:List_of_unsolved_problems_in_computer_science dbr:Polynomial_function dbr:EXPTIME dbr:Cryptocurrency dbr:Graph_isomorphism dbr:Reduction_(complexity) dbr:Graph_isomorphism_problem dbr:Unique_games_conjecture dbr:Game_complexity dbr:Knuth's_up-arrow_notation dbr:Multipartite_graph dbr:William_Gasarch dbr:Co-NP-complete dbr:Oracle_machine dbr:Polynomial_time dbr:Time_hierarchy_theorem dbr:List_of_NP-complete_problems dbr:Information-theoretic_security dbr:Undecidable_problem dbc:1956_in_computing dbc:Conjectures dbc:Mathematical_optimization dbr:Discrete_logarithm_problem dbr:Non-constructive_proof dbr:Traveling_salesman_problem dbc:Computer-related_introductions_in_1956 dbr:Exponential_time dbr:Sharp-P dbr:Linear_order dbr:NP-complete dbr:Quantum_computation dbr:Quasi-polynomial_time dbr:NP-hard dbr:Sharp-P-complete dbr:UT_Austin dbr:RSA_(algorithm) dbr:Quadratic_time dbr:Descriptive_complexity dbr:Deterministic_Turing_machine dbr:Deterministic_computation dbr:Non-deterministic_Turing_machine dbr:Linear_time dbr:Clay_Math_Institute dbr:Moshe_Y._Vardi dbr:Computational_theory dbr:Integer_factorization_problem dbr:One-way_functions dbr:Polynomial-time_many-one_reduction dbr:Polynomial_time_hierarchy dbr:Scientificamerican.com dbr:Prime_factorization dbr:Unsolved_problems_in_computer_science dbr:Symmetric_cipher dbr:File:Complexity_classes.svg dbr:File:KnapsackEmpComplexity.GIF dbr:File:P_np_np-complete_np-hard.svg dbr:Relativizing_proof
dbp:b	no (en)
dbp:commons	no (en)
dbp:d	no (en)
dbp:n	no (en)
dbp:q	P versus NP problem (en)
dbp:s	no (en)
dbp:species	no (en)
dbp:v	no (en)
dbp:voy	no (en)
dbp:wikiPageUsesTemplate	dbt:Cite_book dbt:Garey-Johnson dbt:Millennium_Problems dbt:' dbt:Blockquote dbt:Cbignore dbt:Cite_encyclopedia dbt:Cite_journal dbt:Cite_web dbt:Main dbt:Main_article dbt:Math dbt:Pp-move-indef dbt:Quote dbt:Reflist dbt:See_also dbt:Short_description dbt:Sister_project_links dbt:Tooltip dbt:Unsolved dbt:Use_dmy_dates dbt:ComplexityClasses
dbp:wikt	no (en)
dct:subject	dbc:Structural_complexity_theory dbc:Unsolved_problems_in_mathematics dbc:Unsolved_problems_in_computer_science dbc:Millennium_Prize_Problems dbc:1956_in_computing dbc:Conjectures dbc:Mathematical_optimization dbc:Computer-related_introductions_in_1956
gold:hypernym	dbr:Problem
rdf:type	owl:Thing owl:Thing
rdfs:label	P versus NP problem (en) Problém P versus NP (cs) مسألة كثير حدود وكثير حدود غير قطعي (ar) P versus NP (ca) Πρόβλημα P=NP (el) P-NP-Problem (de) Demando P = NP (eo) P vs NP problema (eu) Problème P ≟ NP (fr) Clases de complejidad P y NP (es) Masalah P versus NP (in) Classi di complessità P e NP (it) P-NP 문제 (ko) P≠NP予想 (ja) P versus NP (pt) P=NP? (sv) Рівність класів P і NP (uk) Равенство классов P и NP (ru) P/NP问题 (zh)
rdfs:seeAlso	dbr:Complexity_class
owl:sameAs	yago-res:P versus NP problem freebase:P versus NP problem wikidata:P versus NP problem dbpedia-de:P versus NP problem dbpedia-es:P versus NP problem dbpedia-it:P versus NP problem dbpedia-tr:P versus NP problem dbpedia-fr:P versus NP problem dbpedia-da:P versus NP problem dbpedia-he:P versus NP problem dbpedia-hu:P versus NP problem dbpedia-ja:P versus NP problem dbpedia-pt:P versus NP problem dbpedia-ro:P versus NP problem dbpedia-ru:P versus NP problem dbpedia-zh:P versus NP problem dbpedia-sv:P versus NP problem dbpedia-vi:P versus NP problem dbpedia-be:P versus NP problem dbpedia-el:P versus NP problem dbpedia-id:P versus NP problem dbpedia-ko:P versus NP problem dbpedia-ca:P versus NP problem dbpedia-ar:P versus NP problem dbpedia-ast:P versus NP problem dbpedia-az:P versus NP problem dbpedia-cs:P versus NP problem dbpedia-eo:P versus NP problem dbpedia-eu:P versus NP problem dbpedia-fa:P versus NP problem dbpedia-fi:P versus NP problem dbpedia-gl:P versus NP problem dbpedia-is:P versus NP problem dbpedia-lmo:P versus NP problem dbpedia-lt:P versus NP problem dbpedia-lv:P versus NP problem dbpedia-ml:P versus NP problem dbpedia-nn:P versus NP problem dbpedia-no:P versus NP problem dbpedia-simple:P versus NP problem dbpedia-sr:P versus NP problem dbpedia-th:P versus NP problem dbpedia-uk:P versus NP problem dbpedia-global:P versus NP problem
prov:wasDerivedFrom	wikipedia-en:P_versus_NP_problem?oldid=1311497021&ns=0
foaf:depiction	wiki-commons:Special:FilePath/Complexity_classes.svg wiki-commons:Special:FilePath/KnapsackEmpComplexity.gif wiki-commons:Special:FilePath/P_np_np-complete_np-hard.svg
foaf:isPrimaryTopicOf	wikipedia-en:P_versus_NP_problem
is dbo:knownFor of	dbr:Scott_Aaronson
is dbo:wikiPageRedirects of	dbr:Algebrization dbr:Algebrization dbr:P_=_NP_problem dbr:P_=_NP_problem dbr:P≟NP dbr:P≟NP_problem dbr:P≠NP dbr:NP=P dbr:NP=P_problem dbr:NP_=_P dbr:NP_conjecture dbr:NP_problem dbr:NP_versus_P_problem dbr:P_?_NP dbr:P_=_NP dbr:P_ dbr:P_=_np dbr:P_Versus_NP dbr:P_Versus_NP_Problem dbr:P_and_NP dbr:P_conjecture dbr:P_is_not_NP dbr:P_v_NP dbr:P_versus_NP dbr:P_vs._NP dbr:P_vs._NP_problem dbr:P_vs_NP dbr:P_vs_NP_problem dbr:P_vs_np dbr:P_≟_NP dbr:P_≠_NP dbr:P!=NP dbr:P/=NP dbr:P/NP_Problem dbr:P dbr:P==NP dbr:P=NP dbr:P dbr:P=NP_problem dbr:P=np dbr:Complexity_classes_P_and_NP dbr:Succinct_problem dbr:Succinct_problems dbr:Vinay_Deolalikar dbr:Vinay_Deolilakar dbr:Smale's_third_problem
is dbo:wikiPageWikiLink of	dbr:Smale's_problems dbr:Holographic_algorithm dbr:Holy_Grail_(disambiguation) dbr:Futurama dbr:Mathematics dbr:Travelling_Salesman_(2012_film) dbr:Algorithm dbr:Computer_science dbr:Schaefer's_dichotomy_theorem dbr:Bucket_queue dbr:PSPACE dbr:Computational_complexity_theory dbr:Ketan_Mulmuley dbr:Boolean_satisfiability_problem dbr:Knapsack_problem dbr:Robert_M._Solovay dbr:Philosophy_of_computer_science dbr:Juliette_Kennedy dbr:Millennium_Prize_Problems dbr:Halting_problem dbr:Parameterized_complexity dbr:Clay_Mathematics_Institute dbr:Timothy_Gowers dbr:Kevin_McCurley_(cryptographer) dbr:Boson_sampling dbr:Hadwiger_number dbr:Complexity_and_Real_Computation dbr:List_of_challenge_awards dbr:List_of_mathematics_awards dbr:In_Pursuit_of_the_Traveling_Salesman dbr:Approximation_algorithm dbr:Computational_learning_theory dbr:Juris_Hartmanis dbr:Karp's_21_NP-complete_problems dbr:Lance_Fortnow dbr:Michael_Sipser dbr:NP_(complexity) dbr:Richard_Lipton dbr:Polynomial_hierarchy dbr:History_of_mathematical_notation dbr:Nondeterministic_Turing_machine dbr:Graph_homomorphism dbr:♯P-complete dbr:Berman–Hartmanis_conjecture dbr:Exponential_time_hypothesis dbr:Cook–Levin_theorem dbr:NP-completeness dbr:BQP dbr:Good_Will_Hunting dbr:The_Great_Mathematical_Problems dbr:Natural_proof dbr:Charlie_Eppes dbr:Epistemic_modal_logic dbr:Constraint_satisfaction_problem dbr:NP-intermediate dbr:Computational_hardness_assumption dbr:Computing_the_permanent dbr:Conjecture dbr:Endre_Szemerédi dbr:List_of_unsolved_problems_in_mathematics dbr:P_(complexity) dbr:Theory_of_computation dbr:Time_complexity dbr:List_of_unsolved_problems_in_computer_science dbr:EXPTIME dbr:Graph_isomorphism dbr:Clique_problem dbr:Bipartite_dimension dbr:2-satisfiability dbr:Gadget_(computer_science) dbr:Unique_games_conjecture dbr:List_of_In_Our_Time_programmes dbr:List_of_films_about_mathematicians dbr:Computational_social_choice dbr:Matroid_oracle dbr:Numerical_sign_problem dbr:Pseudorandom_generator dbr:Uncertainty_Principle_(Numbers) dbr:PPAD_(complexity) dbr:Geometric_complexity_theory dbr:Succinct_(disambiguation) dbr:Galactic_algorithm dbr:Algebrization dbr:NP/poly dbr:P_=_NP_problem dbr:P≟NP dbr:P≟NP_problem dbr:P≠NP dbr:NP=P dbr:NP=P_problem dbr:NP_=_P dbr:NP_conjecture dbr:NP_problem dbr:NP_versus_P_problem dbr:P_?_NP dbr:P_=_NP dbr:P_ dbr:P_=_np dbr:P_Versus_NP dbr:P_Versus_NP_Problem dbr:P_and_NP dbr:P_conjecture dbr:P_is_not_NP dbr:P_v_NP dbr:P_versus_NP dbr:P_vs._NP dbr:P_vs._NP_problem dbr:P_vs_NP dbr:P_vs_NP_problem dbr:P_vs_np dbr:P_≟_NP dbr:P_≠_NP dbr:P!=NP dbr:P/=NP dbr:P/NP_Problem dbr:P dbr:P==NP dbr:P=NP dbr:P dbr:P=NP_problem dbr:P=np dbr:Complexity_classes_P_and_NP dbr:Succinct_problem dbr:Succinct_problems dbr:Vinay_Deolalikar dbr:Vinay_Deolilakar dbr:Smale's_third_problem
is rdfs:seeAlso of	dbr:NP-completeness
is foaf:primaryTopic of	wikipedia-en:P_versus_NP_problem