Lista problemelor nerezolvate din informatică

Acest articol este o listă de probleme notabile nerezolvate din informatică. O problemă în informatică este considerată nerezolvată atunci când nu se cunoaște nicio soluție sau când experții în domeniu nu sunt de acord cu soluțiile propuse.

Complexitatea computațională

• Problema P versus NP
• Care este relația dintre BQP și NP ?
• Problema NC = P
• Problema NP = co-NP
• problema P = BPP
• problema P = PSPACE
• problema L = NL
• problema PH = PSPACE
• problema L = P
• problema L = RL
• Conjectura jocurilor unice
• Este adevărată ipoteza timpului exponenţial?
  • Este adevărată ipoteza tare a timpului exponențial (SETH)?
• Există funcții unidirecționale ?
  • Este posibilă criptografia cu cheie publică?
• Conjectura log-rang

Timp polinomial versus nepolinomial pentru probleme algoritmice specifice

• Se poate face factorizarea întregilor în timp polinomial pe un computer clasic (necuantic)?
• Logaritmul discret poate fi calculat în timp polinomial pe un computer clasic (necuantic)?
• Poate fi calculat cel mai scurt vector al unei rețele în timp polinomial pe un computer clasic sau cuantic?
• Pot fi identificate desene planare grupate în timp polinomial?
• Problema izomorfismului grafurilor poate fi rezolvată în timp polinomial?
• Pot fi recunoscute puterile frunzelor și k-frunzelor în timp polinomial?
• Pot fi rezolvate jocurile de paritate în timp polinomial?
• Distanța de rotație dintre doi arbori binari poate fi calculată în timp polinomial?
• Pot fi recunoscute în timp polinomial grafuri cu lățime de clică mărginită?^[1]
• Se poate găsi o cvasigeodezică închisă simplă pe un poliedru convex în timp polinomial? ^[2]
• Poate fi găsită în timp polinomial o încorporare simultană cu muchii fixe pentru două grafice date? ^[3]

Alte probleme algoritmice

• Conjectura optimității dinamice: arborii splay au un raport competitiv mărginit?
• Există un algoritm online k-competitiv pentru problema celor k-servere ?
• Poate fi construit un arbore de căutare în adâncime în NC ?
• Poate fi calculată transformata Fourier rapidă în timp o(n log n)?
• Care este cel mai rapid algoritm pentru înmulțirea a două numere cu n cifre?
• Care este cea mai mică complexitate posibilă în timp pe cazul mediu a lui Shellsort cu o secvență de goluri deterministă, fixă?
• Poate fi rezolvat 3SUM în timp sub-pătratic tare, adică în timp O(n^2−ϵ) pentru un ϵ>0 ?
• Distanța de editare dintre două șiruri de lungime n poate fi calculată în timp sub-pătratic tare? (Acest lucru este posibil numai dacă ipoteza tare a timpului exponențial este falsă. )
• Se poate face sortarea X + Y în timp o(n² log n)?
• Care este cel mai rapid algoritm pentru multiplicarea matricelor?
• Pot fi calculate drumurile cele mai scurte pe toate perechile în timp sub-cubic tare, adică în timp O(V^3−ϵ) pentru ϵ>0 ?
• Poate fi derandomizată lema Schwartz-ZIPPEL pentru testarea identității polinomiale?
• Admite programarea liniară un algoritm de timp puternic polinomial? (Aceasta este problema nr. 9 din lista de probleme ale lui Smale.)
• Câte întrebări sunt necesare pentru tăierea tortului fără invidie?
• Care este algoritmul pentru tabela de corespondență care generează în mod constant labirinturi jucabile în jocul Atari 2600 Entombed din 1982 doar din valorile celor cinci pixeli adiacenți următorilor care urmează să fie generați?
• Care este complexitatea algoritmică a problemei arborelui minim de acoperire? În mod echivalent, care este complexitatea arborelui de decizie a problemei AMA? Algoritmul optim pentru calcularea AMA-urilor este cunoscut, dar se bazează pe arbori de decizie, astfel încât complexitatea sa este necunoscută.

Algoritmi de procesare a limbajului natural

• Există un algoritm de despărțire în silabe perfect pentru limba engleză?
• Există un algoritm de stemming perfect pentru limba engleză?
• Există un algoritm perfect de despărțire a frazelor în propoziții pentru limba engleză?
• Cum pot computerele să discerne ambiguitatea pronumelui în limba engleză? (Cunoscută și sub numele de Provocarea Scheme Winograd).

Teoria limbajelor de programare

• POPLmark
• Conjectura Barendregt–Geuvers–Klop

Alte probleme

• Conjectura Aanderaa–Karp–Rosenberg
• Conjectura Černý
• Problema generalizată a înălțimii stelelor
• Problema separării cuvintelor

Note

1. Fellows, Michael R.; Rosamond, Frances A.; Rotics, Udi; Szeider, Stefan (2009), „Clique-width is NP-complete” (PDF), SIAM Journal on Discrete Mathematics, 23 (2), pp. 909–939, doi:10.1137/070687256, MR 2519936, arhivat din original (PDF) la 27 februarie 2019 .
2. 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 .
3. 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, 4271, Berlin: Springer, pp. 325–335, doi:10.1007/11917496_29, MR 2290741, arhivat din original (PDF) la 22 octombrie 2021, accesat în 5 noiembrie 2021 .

Legături externe

• Probleme deschise în jurul algoritmilor exacți de Gerhard J. Woeginger, Discrete Applied Mathematics 156 (2008) 397–405.
• Lista RTA a problemelor deschise – probleme deschise în rescriere.
• Lista TLCA a problemelor deschise – probleme deschise în calculul lambda tipat.