List of unsolved problems in computer science

This article is a list of notable unsolved problems in computer science. A problem in computer science is considered unsolved when no solution is known or when experts in the field disagree about proposed solutions.

Computational complexity

P versus NP problem
What is the relationship between BQP and NP?
NC = P problem
NP = co-NP problem
P = BPP problem
P = PSPACE problem
L = NL problem
PH = PSPACE problem
L = P problem
L = RL problem
Unique games conjecture
Is the exponential time hypothesis true?
- Is the strong exponential time hypothesis (SETH) true?
Do one-way functions exist?
- Is public-key cryptography possible?
Log-rank conjecture

Polynomial versus nondeterministic-polynomial time for specific algorithmic problems

Can integer factorization be done in polynomial time on a classical (non-quantum) computer?
Can the discrete logarithm be computed in polynomial time on a classical (non-quantum) computer?
Can the shortest vector of a lattice be computed in polynomial time on a classical or quantum computer?
Can the graph isomorphism problem be solved in polynomial time on a classical computer?
Is graph canonization polynomial time equivalent to the graph isomorphism problem?
Can leaf powers and $k$ -leaf powers be recognized in polynomial time?
Can parity games be solved in polynomial time?
Can the rotation distance between two binary trees be computed in polynomial time?
Can graphs of bounded clique-width be recognized in polynomial time?^[1]
Can one find a simple closed quasigeodesic on a convex polyhedron in polynomial time?^[2]
Can a simultaneous embedding with fixed edges for two given graphs be found in polynomial time?^[3]
Can the square-root sum problem be solved in polynomial time in the Turing machine model?

Other algorithmic problems

The dynamic optimality conjecture: Do splay trees have a bounded competitive ratio?
Can a depth-first search tree be constructed in NC?
Can the fast Fourier transform be computed in $o (n log n)$ time?
What is the fastest algorithm for multiplication of two n-digit numbers?
What is the lowest possible average-case time complexity of Shellsort with a deterministic fixed gap sequence?
Can 3SUM be solved in strongly sub-quadratic time, that is, in time $O (n 2-ϵ)$ for some $ϵ>0$ ?
Can the edit distance between two strings of length $n$ be computed in strongly sub-quadratic time? (This is only possible if the strong exponential time hypothesis is false.)
Can X + Y sorting be done in $o (n 2 log n)$ time?
What is the fastest algorithm for matrix multiplication?
Can all-pairs shortest paths be computed in strongly sub-cubic time, that is, in time $O (V 3-ϵ)$ for some $ϵ>0$ ?
Can the Schwartz–Zippel lemma for polynomial identity testing be derandomized?
Does linear programming admit a strongly polynomial-time algorithm? (This is problem #9 in Smale's list of problems.)
How many queries are required for envy-free cake-cutting?
What is the algorithmic complexity of the minimum spanning tree problem? Equivalently, what is the decision tree complexity of the MST problem? The optimal algorithm to compute MSTs is known, but it relies on decision trees, so its complexity is unknown.
Gilbert–Pollak conjecture: Is the Steiner ratio of the Euclidean plane equal to $2/{\sqrt {3}}$ ?

Programming language theory

Barendregt–Geuvers–Klop conjecture

Other problems

Is the Aanderaa–Karp–Rosenberg conjecture true?
Černý Conjecture: If a deterministic finite automaton with $n$ states has a synchronizing word, must it have one of length at most $(n-1)^{2}$ ?
Generalized star-height problem: Can all regular languages be expressed using generalized regular expressions with a limited nesting depth of Kleene stars?
Separating words problem: How many states are needed in a deterministic finite automaton that behaves differently on two given strings of length $n$ ?
What is the Turing completeness status of all unique elementary cellular automata?
The problem to determine all positive integers $n$ such that the concatenation of $n$ and $n^{2}$ in base $b$ uses at most $k$ distinct characters for $b$ and $k$ fixed^{[citation needed]} and many other problems in the coding theory are also the unsolved problems in mathematics.

References

^ Fellows, Michael R.; Rosamond, Frances A.; Rotics, Udi; Szeider, Stefan (2009), "Clique-width is NP-complete" (PDF), SIAM Journal on Discrete Mathematics, 23 (2): 909–939, doi:10.1137/070687256, MR 2519936, S2CID 18055798, archived from the original (PDF) on 2019-02-27.
^ Demaine, Erik D.; O'Rourke, Joseph (2007), "24 Geodesics: Lyusternik–Schnirelmann", Geometric folding algorithms: Linkages, origami, polyhedra, Cambridge: Cambridge University Press, pp. 372–375, doi:10.1017/CBO9780511735172, ISBN 978-0-521-71522-5, MR 2354878.
^ Gassner, Elisabeth; Jünger, Michael; Percan, Merijam; Schaefer, Marcus; Schulz, Michael (2006), "Simultaneous graph embeddings with fixed edges" (PDF), Graph-Theoretic Concepts in Computer Science: 32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006, Revised Papers (PDF), Lecture Notes in Computer Science, vol. 4271, Berlin: Springer, pp. 325–335, doi:10.1007/11917496_29, ISBN 978-3-540-48381-6, MR 2290741.

External links

Open problems around exact algorithms by Gerhard J. Woeginger, Discrete Applied Mathematics 156 (2008) 397–405.
The RTA list of open problems – open problems in rewriting.
The TLCA List of Open Problems – open problems in area typed lambda calculus.

v t e Well-known unsolved problems by discipline
Astronomy Biology Chemistry Computer science Economics Fair division Geoscience Information theory Mathematics Medicine Neuroscience Physics Statistics

Read other articles:

Sisters of Social Service

Sisters of Social Service

The Sisters of Social Service (SSS; Hungarian: Szociális Testvérek Társasága, Latin: Societas Sororum Socialium) are a Roman Catholic religious institute of women founded in Hungary in 1923 by Margit Slachta. The sisters adopted the social mission of the Catholic Church and Benedictine spirituality with a special devotion to the Holy Spirit.[1] Foundation Margit Slachta in 1946 The institute was founded by Margit Slachta, a pioneer in social services and a leading Hungarian politi...

Fredric Jameson

Fredric Jameson

Fredric JamesonLahir14 April 1934 (umur 89)Cleveland, Ohio, Amerika SerikatAlmamaterHaverford CollegeUniversitas YaleEraFilsafat abad ke-20/21KawasanFilsafat BaratAliranMarxisme BaratHermeneutika Marxis[1]Minat utamaPascamodernisme · modernisme · fiksi ilmiah · utopia · sejarah · naratif · kajian budaya · dialektika · strukturalismeGagasan pentingPemetaan kognitif · alego...

Annibale Carracci

Annibale Carracci

Annibale CarracciPotret diri (Uffizi)Lahir3 November 1560Bologna, Negara GerejaMeninggal15 Juli 1609(1609-07-15) (umur 48)Roma, Negara GerejaKebangsaanItaliaDikenal atasLukisanGerakan politikBarok Annibale Carracci (pengucapan bahasa Italia: [anˈniːbale karˈrattʃi]; 3 November 1560 – 15 Juli 1609) adalah seorang pelukis dan pengajar asal Italia yang aktif di Bologna dan kemudian di Roma. Bersama dengan para saudaranya, Annibale adalah salah satu tokoh penting, j...

مرحلة المجموعات في الدوري الأوروبي 2011–12

مرحلة المجموعات في الدوري الأوروبي 2011–12

المقالة الرئيسة: دوري أوروبا 2011–12 هذه الصحفة تقدم تفاصيل دور المجموعات من دوري أوروبا 2011–12. سوف يشمل دور المجموعات 48 فريق: 38 فائز من الدور الفاصل، و10 فرق خاسرة من الدور الفاصل لدوري الأبطال.[1] سيتم تقسيم هذه الفرق إلى اثني عشر مجموعة من أربعة، حيث سيلعبون ضد بعضهم البع�...

Первородный грех

Первородный грех

Об экономическом термине см. Первородный грех (экономика). ХристианствоБиблия Ветхий Завет Новый Завет Евангелие Десять заповедей Нагорная проповедь Апокрифы Бог, Троица Бог Отец Иисус Христос Святой Дух История христианства Апостолы Хронология христианства Ран�...

First Lady of Poland

First Lady of Poland

First Lady of PolandPierwsza dama PolskiIncumbentAgata Kornhauser-Dudasince 6 August 2015ResidencePresidential PalaceInaugural holderMaria PiłsudskaFormation14 November 1918WebsiteFirst Lady of Poland (Pierwsza Dama) First Lady of the Republic of Poland is an informal designation customarily applied to the wife of the president of the Republic of Poland (as so far all Polish president had wives). The First Lady does not hold a constitutional position and there are no political duties as...

Mercy (Madame Monsieur song)

Mercy (Madame Monsieur song)

2018 song written and performed by Madame Monsieur MercySingle by Madame Monsieurfrom the album Vu d'ici Released20 January 2018GenreElectropopFrench popLength3:58LabelLow WoodPlay TwoSongwriter(s)Émilie SattJean-Karl LucasProducer(s)Émilie SattJean-Karl LucasMadame Monsieur singles chronology Tournera (2016) Mercy (2018) Comme une reine (2018) Audio samplefilehelpMusic videoMercy on YouTubeEurovision Song Contest 2018 entryCountryFranceArtist(s)Madame MonsieurLanguageFrenchComposer(s)Émil...

Riccardo Tozzi (arbitro)

Riccardo Tozzi (arbitro)

Riccardo Tozzi Informazioni personali Arbitro di Calcio Sezione Ostia Lido Professione Imprenditore Attività nazionale Anni Campionato Ruolo 2005-20082008-20102010-2013 Serie C1 e C2Serie A e BSerie B ArbitroArbitroArbitro Riccardo Tozzi (Roma, 28 gennaio 1975) è un ex arbitro di calcio italiano. Lasciati i campi, continua a far parte dell'A.I.A come dirigente e dal 1º luglio 2014 è vice presidente del C.R.A. Lazio Carriera Appartenente alla Sezione AIA di Ostia Lido, diventa arbitro eff...

Sonny with a Chance

Sonny with a ChanceGenreSitkom remajaPembuatSteve MarmelPemeran Demi Lovato Tiffany Thornton Sterling Knight Brandon Mychal Smith Doug Brochu Allisyn Ashley Arm Lagu pembukaSo Far, So Great oleh Demi LovatoPenata musik Chris Alan Lee Scott Clausen Danny Jacob Negara asalAmerika SerikatBahasa asliInggrisJmlh. musim2Jmlh. episode47 (daftar episode)ProduksiProduser eksekutif Brian Robbins Sharla Sumpter Bridgett Michael Feldman Steve Marmel ProduserPatty Gary CoxPengaturan kameraMulti-cam...

Madhav Kumar Nepal

Madhav Kumar Nepal

Former Prime Minister of Nepal HonourableMadhav Kumar Nepalमाधवकुमार नेपाल34th Prime Minister of NepalIn office25 May 2009 – 6 February 2011PresidentRam Baran YadavDeputyBijay Kumar GachhadarPreceded byPushpa Kamal DahalSucceeded byJhala Nath KhanalDeputy Prime Minister of NepalIn office30 November 1994 – 12 September 1995MonarchKing BirendraPrime MinisterMan Mohan AdhikariChairman of CPN (Unified Socialist) and Socialist FrontIncumbentAssumed...

أورنج المغرب

أورنج المغربأورنج المغربالشعارمعلومات عامةالبلد المغربالتأسيس 1999 (تحت اسم ميدي تيليكوم أو ميديتل)النوع اتصالاتالشكل القانوني شركة مساهمة عامة (S.A) المقر الرئيسي الدار البيضاء، المملكة المغربيةموقع الويب orange.ma المنظومة الاقتصاديةالشركة الأم أورنجالصناعة صناعة الاتص...

Juggernaut Books

Juggernaut Books

Juggernaut BooksDidirikanSeptember 2015PendiriChiki Sarkar, Durga RaghunathNegara asalIndiaKantor pusatNew Delhi, IndiaDistribusiDaring dan fisikTokoh kunciSimran Khara, Nandan Nilekani, Aveek Sarkar, Pratap Bhanu Mehta, Neeraj Aggarwal, Gavin Morris, Jaishree Ram Mohan, Nandini MehtaJenis terbitanPenerbitan daring, cerita pendek, otobiografi, buku elektronikSitus resmiwww.juggernaut.in Juggernaut Books (secara informal Juggernaut) adalah rumah penerbitan buku digital yang berkantorpusatkan d...

Calista Flockhart

Calista Flockhart

American actress (born 1964) Calista FlockhartFlockhart in 2009BornCalista Kay Flockhart (1964-11-11) November 11, 1964 (age 59)Freeport, Illinois, U.S.Alma materRutgers University, New Brunswick (BFA)OccupationActressYears active1989–presentKnown forAlly McBealBrothers & SistersA Midsummer Night's DreamSupergirlThe BirdcageSpouse Harrison Ford (m. 2010)Children1 Calista Kay Flockhart (born November 11, 1964)[1][2] is an...

Roman Catholic Diocese of Townsville

Roman Catholic Diocese of Townsville

Latin Catholic diocese in Australia Diocese of TownsvilleDioecesis TovnsvillensisSacred Heart Cathedral, Townsville,taken in 1903 after Cyclone LeontaLocationCountryAustraliaTerritoryNorth QueenslandEcclesiastical provinceBrisbaneCoordinates19°15′32″S 146°48′42″E / 19.25889°S 146.81167°E / -19.25889; 146.81167StatisticsArea435,200 km2 (168,000 sq mi)Population- Total- Catholics(as of 2004) 252,289 74,084 ( 29.4%%)Parishes 27Inf...

タラスコ語

タラスコ語プレペチャ語 P'urhépecha発音 IPA: [pʰuˈɽepet͡ʃa]話される国メキシコ地域ミチョアカン州民族タラスコ族話者数 13万5000人（2005年）[1]言語系統「タラスコ語族」または孤立した言語タラスコ語表記体系ラテン文字言語コードISO 639-1 -ISO 639-2 -ISO 639-3 各種:pua — Western Highland Purepechatsz — PurepechaLinguist List pua Purepecha tsz TrascanGlottolog ...

Belgique au Concours Eurovision de la chanson 2008

Belgique au Concours Eurovision de la chanson 2008

Cet article est une ébauche concernant la Belgique et le Concours Eurovision de la chanson. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. La Belgique a participé au Concours Eurovision de la chanson 2008 à Belgrade, en Serbie. C'est la 50e participation belge au Concours Eurovision de la chanson. Belgiqueau Concours Eurovision 2008 Le groupe Ishtar représentant la Belgique avec la chanson O julissi na jali...

映画妖怪ウォッチシャドウサイド鬼王の復活

映画妖怪ウォッチシャドウサイド鬼王の復活

妖怪ウォッチ > 映画妖怪ウォッチシャドウサイド鬼王の復活妖怪ウォッチシャドウサイド > 映画妖怪ウォッチシャドウサイド鬼王の復活映画妖怪ウォッチシャドウサイド鬼王の復活監督ウシロシンジ脚本日野晃博原案日野晃博原作レベルファイブ製作総指揮日野晃博出演者上白石萌音千葉雄大田村睦心関智一黒田崇矢木村良平子安武人福山潤石�...

Oratory of Jesus

Oratory of Jesus

Catholic society of apostolic life Cardinal Pierre de Bérulle, founder of the French Oratory The Congregation of the Oratory of Jesus and Mary Immaculate (French: Société de l'Oratoire de Jésus et de Marie Immaculée, Latin: Congregatio Oratorii Iesu et Mariæ), best known as the French Oratory or Oratory of Jesus, is a society of apostolic life of Catholic priests founded in 1611 in Paris, France, by Pierre de Bérulle (1575–1629), who later became a cardinal . Members are known as Bé...

FIBT World Championships 2009

FIBT World Championships 2009

2009 World ChampionshipsLocationLake Placid, New YorkDatesFebruary 20-March 1← Altenberg 2008Königssee 2011 → The FIBT World Championships 2009, officially known as the Bauhaus FIBT Bobsleigh & Skeleton World Championships, February 20 to March 1, 2009, at the bobsleigh, luge, and skeleton track in Lake Placid, New York, for the ninth time, doing so previously in 1949, 1961, 1969, 1973, 1978, 1983, 1997 (skeleton), and 2003 (men's bobsleigh). Lake Placid was chosen ...

Endangered language

Endangered language

Language that is at risk of going extinct More than 50% of the world's endangered languages are located in just eight countries (denoted in red on the map): India, Brazil, Mexico, Australia, Indonesia, Nigeria, Papua New Guinea and Cameroon. In such countries and around them are the areas that are the most linguistically diverse in the world (denoted in blue on the map).Language death can be the result of language shift in which ethnic group members no longer learn their heritage language as ...