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://archive.org/details/computersintract0000gare https://www.youtube.com/watch%3Fv=YX40hbAHx3s http://www.wisdom.weizmann.ac.il/~oded/bc-drafts.html https://www2.eecs.berkeley.edu/Pubs/TechRpts/2017/EECS-2017-146.pdf https://www.scientificamerican.com/article/the-top-unsolved-questions-in-mathematics-remain-mostly-mysterious/ https://www.britannica.com/science/P-versus-NP-problem https://awards.acm.org/about/2017-doctoral-dissertation https://www.claymath.org/millennium-problems/p-vs-np-problem http://weblog.fortnow.com https://ghostarchive.org/varchive/youtube/20211124/YX40hbAHx3s%7C
dbo:wikiPageWikiLink	dbr:Discrete_logarithm_problem dbr:Knapsack_problem dbr:Co-NP-complete dbr:Oracle_machine dbr:Relativizing_proof dbr:Stephen_Cook dbr:Latin_square dbc:Structural_complexity_theory dbc:Unsolved_problems_in_computer_science dbr:Philosophy dbr:Elementary_(TV_series) dbr:Cornell_University dbr:Composite_number dbr:Peano_axioms dbr:Millennium_Prize_Problems dbr:Signature_(logic) dbr:Karp's_21_NP-complete_problems dbr:Multipartite_graph dbr:List_of_NP-complete_problems dbr:Artificial_intelligence dbr:First-order_logic dbr:Association_for_Computing_Machinery dbr:National_Security_Agency dbr:Universal_quantification dbr:NP_(complexity) dbr:Fixed-point_combinator dbr:AKS_primality_test dbr:Graph_isomorphism dbr:Cook–Levin_theorem dbc:Millennium_Prize_Problems dbr:Linear_programming dbr:Public-key_cryptography dbr:Anil_Nerode dbr:PSPACE dbr:Robert_M._Solovay dbr:Polynomial_hierarchy dbr:EXPTIME dbr:Treehouse_of_Horror_VI dbr:Independence_(mathematical_logic) dbr:Blockchain dbr:Big_O_notation dbc:Unsolved_problems_in_mathematics dbr:MIT_Press dbr:Game_complexity dbr:Protein_structure_prediction dbr:Subset_sum_problem dbr:Chess dbr:Cryptography dbr:Encyclopædia_Britannica dbr:The_Simpsons dbr:YouTube dbr:Operations_research dbr:Scott_Aaronson dbr:Integer_programming dbr:Halting_problem dbr:Co-NP dbr:Presburger_arithmetic dbr:List_of_unsolved_problems_in_computer_science dbr:Algorithmic_efficiency dbr:Algorithm dbc:Conjectures dbr:Economics dbr:Game_theory dbc:Mathematical_optimization dbr:Theoretical_computer_science dbr:Certificate_(complexity) dbr:Cobham's_thesis dbr:Computer_science dbr:Donald_Knuth dbr:John_von_Neumann dbr:Kurt_Gödel dbr:Alexander_Razborov dbr:Avi_Wigderson dbr:Leonid_Levin dbr:László_Babai dbr:Steven_Rudich dbr:Michael_O._Rabin dbr:Bitcoin dbr:Fermat's_Last_Theorem dbr:John_Forbes_Nash_Jr. dbr:Advanced_Encryption_Standard dbr:Computational_complexity_theory dbr:Quantum_algorithm dbr:Linear_order dbr:Sharp-P dbr:Polynomial dbr:Polynomial_function dbr:Sudoku dbr:Boolean_satisfiability_problem dbc:1956_in_computing dbr:General_number_field_sieve dbr:Simplex_algorithm dbr:Triple_DES dbr:Quasi-polynomial_time dbr:Complexity_class dbr:Graph_minor dbr:Knuth's_up-arrow_notation dbr:Reduction_(complexity) dbr:Non-constructive_proof dbr:List_of_Elementary_episodes dbr:Travelling_Salesman_(2012_film) dbr:Unique_games_conjecture dbr:Entscheidungsproblem dbr:Cryptographic_hash_function dbr:List_of_unsolved_problems_in_mathematics dbr:P_(complexity) dbr:Rice_University dbr:Theory_of_computation dbr:Information-theoretic_security dbr:Undecidable_problem dbr:Graph_isomorphism_problem dbr:Average-case_complexity dbr:String_(computer_science) dbr:Time_complexity dbr:IP_(complexity) dbc:Computer-related_introductions_in_1956 dbr:Clay_Mathematics_Institute dbr:Time_hierarchy_theorem dbr:RSA_(algorithm) dbr:Computer_programming dbr:Princeton_University dbr:Turing_machine dbr:Graph_(discrete_mathematics) dbr:Cryptocurrency dbr:Travelling_salesman_problem dbr:Randomized_algorithm dbr:Shor's_algorithm dbr:Second-order_logic dbr:Michael_J._Fischer dbr:Natural_proof dbr:Decision_problem dbr:UT_Austin dbr:ZFC dbr:Quantum_complexity_theory dbr:Russell_Impagliazzo dbr:W._H._Freeman_and_Company dbr:William_Gasarch dbr:Quantum_computation dbr:Traveling_salesman_problem dbr:NP-complete dbr:NP-hard dbr:Sharp-P-complete dbr:Polynomial_time dbr:Exponential_time dbr:Linear_time dbr:Gerhard_J._Woeginger dbr:Richard_E._Ladner dbr:PH_(complexity) dbr:Non-deterministic_Turing_machine dbr:Moshe_Y._Vardi dbr:One-way_functions dbr:File:Complexity_classes.svg dbr:File:KnapsackEmpComplexity.GIF dbr:Prime_factorization dbr:Descriptive_complexity dbr:Deterministic_Turing_machine dbr:Deterministic_computation dbr:Clay_Math_Institute dbr:Computational_theory dbr:Integer_factorization_problem dbr:Quadratic_time dbr:Scientificamerican.com dbr:Symmetric_cipher dbr:Polynomial-time_many-one_reduction dbr:Polynomial_time_hierarchy dbr:Unsolved_problems_in_computer_science dbr:File:P_np_np-complete_np-hard.svg
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:Quote dbt:Cite_book dbt:Cite_web dbt:Main dbt:Reflist dbt:Math dbt:Cite_journal dbt:ComplexityClasses dbt:See_also dbt:Pp-move-indef dbt:Sister_project_links dbt:Use_dmy_dates dbt:Garey-Johnson dbt:Cbignore dbt:Cite_encyclopedia dbt:Millennium_Problems dbt:' dbt:Main_article dbt:Unsolved dbt:Tooltip dbt:Short_description dbt:Blockquote
dbp:wikt	no (en)
dct:subject	dbc:Structural_complexity_theory dbc:Unsolved_problems_in_computer_science dbc:Millennium_Prize_Problems dbc:Unsolved_problems_in_mathematics dbc:Conjectures dbc:Mathematical_optimization dbc:1956_in_computing dbc:Computer-related_introductions_in_1956
gold:hypernym	dbr:Problem
rdfs:label	P versus NP problem (en) مسألة كثير حدود وكثير حدود غير قطعي (ar) P versus NP (ca) Πρόβλημα P=NP (el) Problém P versus NP (cs) 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予想 (ja) P-NP 문제 (ko) P versus NP (pt) P=NP? (sv) Равенство классов P и NP (ru) Рівність класів P і NP (uk) P/NP问题 (zh)
rdfs:seeAlso	dbr:Complexity_class
owl:sameAs	freebase:P versus NP problem yago-res:P versus NP problem wikidata:P versus NP problem dbpedia-it:P versus NP problem dbpedia-de:P versus NP problem dbpedia-fr:P versus NP problem dbpedia-tr:P versus NP problem dbpedia-zh:P versus NP problem dbpedia-ja:P versus NP problem dbpedia-pt:P versus NP problem dbpedia-he:P versus NP problem dbpedia-ro:P versus NP problem dbpedia-da:P versus NP problem dbpedia-es:P versus NP problem dbpedia-hu:P versus NP problem dbpedia-fa:P versus NP problem dbpedia-ru:P versus NP problem dbpedia-sv:P versus NP problem dbpedia-vi:P versus NP problem dbpedia-ko:P versus NP problem dbpedia-id:P versus NP problem dbpedia-be:P versus NP problem dbpedia-el: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-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 dbr:P versus NP problem
prov:wasDerivedFrom	wikipedia-en:P_versus_NP_problem?oldid=1287287306&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: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:Smale's_third_problem dbr:Complexity_classes_P_and_NP dbr:P≟NP dbr:P≟NP_problem dbr:P≠NP dbr:Succinct_problem dbr:Succinct_problems dbr:Vinay_Deolalikar dbr:Vinay_Deolilakar
is dbo:wikiPageWikiLink of	dbr:Parameterized_complexity dbr:Knapsack_problem dbr:List_of_films_about_mathematicians dbr:Juliette_Kennedy dbr:NP-completeness dbr:Epistemic_modal_logic dbr:Constraint_satisfaction_problem dbr:NP-intermediate dbr:Millennium_Prize_Problems dbr:Karp's_21_NP-complete_problems dbr:Charlie_Eppes dbr:NP_(complexity) dbr:Philosophy_of_computer_science dbr:Graph_isomorphism dbr:Conjecture dbr:Cook–Levin_theorem dbr:PSPACE dbr:Robert_M._Solovay dbr:Polynomial_hierarchy dbr:EXPTIME dbr:Hadwiger_number dbr:Futurama dbr:History_of_mathematical_notation dbr:Berman–Hartmanis_conjecture dbr:Matroid_oracle dbr:Mathematics dbr:Good_Will_Hunting dbr:Exponential_time_hypothesis dbr:Galactic_algorithm dbr:Halting_problem dbr:♯P-complete dbr:Clique_problem dbr:List_of_unsolved_problems_in_computer_science dbr:Nondeterministic_Turing_machine dbr:List_of_In_Our_Time_programmes dbr:Algorithm dbr:Boson_sampling dbr:Complexity_and_Real_Computation dbr:Computer_science dbr:Juris_Hartmanis dbr:Lance_Fortnow dbr:Michael_Sipser dbr:Computational_complexity_theory dbr:Boolean_satisfiability_problem dbr:Pseudorandom_generator dbr:Numerical_sign_problem dbr:Travelling_Salesman_(2012_film) dbr:Uncertainty_Principle_(Numbers) dbr:Unique_games_conjecture dbr:Approximation_algorithm dbr:Endre_Szemerédi dbr:BQP dbr:Timothy_Gowers dbr:List_of_unsolved_problems_in_mathematics dbr:P_(complexity) dbr:Theory_of_computation dbr:Schaefer's_dichotomy_theorem dbr:PPAD_(complexity) dbr:Time_complexity dbr:Ketan_Mulmuley dbr:Kevin_McCurley_(cryptographer) dbr:Clay_Mathematics_Institute dbr:Graph_homomorphism dbr:Bipartite_dimension dbr:Holographic_algorithm dbr:Holy_Grail_(disambiguation) dbr:Richard_Lipton dbr:2-satisfiability dbr:Gadget_(computer_science) dbr:Natural_proof dbr:Algebrization dbr:Computational_learning_theory dbr:Smale's_problems dbr:Computational_hardness_assumption dbr:Computing_the_permanent dbr:Bucket_queue dbr:Succinct_(disambiguation) dbr:NP/poly dbr:The_Great_Mathematical_Problems dbr:List_of_mathematics_awards dbr:List_of_challenge_awards dbr:Computational_social_choice dbr:P_=_NP_problem dbr:Geometric_complexity_theory dbr:In_Pursuit_of_the_Traveling_Salesman 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:Smale's_third_problem dbr:Complexity_classes_P_and_NP dbr:P≟NP dbr:P≟NP_problem dbr:P≠NP dbr:Succinct_problem dbr:Succinct_problems dbr:Vinay_Deolalikar dbr:Vinay_Deolilakar
is rdfs:seeAlso of	dbr:NP-completeness
is foaf:primaryTopic of	wikipedia-en:P_versus_NP_problem