Liste over uløste problemer inden for datalogi - List of unsolved problems in computer science
Denne artikel er en liste over bemærkelsesværdige uløste problemer inden for datalogi . Et problem inden for datalogi betragtes som uløst, når der ikke kendes nogen løsning, eller når eksperter på området er uenige om foreslåede løsninger.
Beregningskompleksitet
- P versus NP problem
- Hvad er forholdet mellem BQP og 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
- Unikke formodninger om spil
- Er den eksponentielle tidshypotese sand?
- Er den stærke eksponentielle tidshypotese (SETH) sand?
- Gør envejs funktioner eksisterer?
- Er kryptografi med offentlig nøgle mulig?
- Log-rang formodning
Polynom kontra ikke-polynomisk tid til specifikke algoritmiske problemer
- Kan heltalsfaktorisering foretages på polynomisk tid på en klassisk (ikke-kvant) computer?
- Kan den diskrete logaritme beregnes på polynomisk tid på en klassisk (ikke-kvante) computer?
- Kan den korteste vektor af et gitter beregnes på polynomisk tid på en klassisk eller kvantecomputer?
- Kan klyngede plane tegninger findes på polynomisk tid?
- Kan grafisomorfismen løses på polynomisk tid?
- Kan blad beføjelser og k -leaf beføjelser anerkendes i polynomiel tid?
- Kan paritetsspil løses på polynomisk tid?
- Kan rotationsafstanden mellem to binære træer beregnes på polynomisk tid?
- Kan grafer med afgrænset klikbredde genkendes på polynomisk tid?
- Kan man finde en simpel lukket quasigeodesic på en konveks polyeder i polynomisk tid?
- Kan en samtidig indlejring med faste kanter for to givne grafer findes på polynomisk tid?
Andre algoritmiske problemer
- Den dynamiske optimalt formodning : har splay træer et begrænset konkurrenceforhold?
- Er der en k -konkurrencedygtig online -algoritme til k -serverproblemet ?
- Kan et dybde-første søgetræ konstrueres i NC ?
- Kan den hurtige Fourier -transformation beregnes på o ( n log n ) tid?
- Hvad er den hurtigste algoritme til multiplikation af to n -cifrede tal?
- Hvad er den lavest mulige gennemsnitlige case-tidskompleksitet for Shellsort med en deterministisk, fast gap-sekvens?
- Kan 3SUM løses i stærkt subkvadratisk tid, det vil sige i tiden O ( n 2 − ϵ ) for nogle ϵ> 0 ?
- Kan redigeringsafstanden mellem to strenge med længde n beregnes i stærkt sub-kvadratisk tid? (Dette er kun muligt, hvis den stærke eksponentielle tidshypotese er falsk.)
- Kan X + Y sortering foretages på o ( n 2 log n ) tid?
- Hvad er den hurtigste algoritme til matrixmultiplikation ?
- Kan alle pars korteste stier beregnes i stærkt sub-kubisk tid, det vil sige i tiden O ( V 3 − ϵ ) for nogle ϵ> 0 ?
- Kan Schwartz-Zippel lemmaet for polynomiel identitet test blive derandomized ?
- Indrømmer lineær programmering en stærkt polynomisk algoritme? (Dette er problem nr. 9 i Smales liste over problemer.)
- Hvor mange forespørgsler er nødvendige for misundelsesfri kageskæring ?
- Hvad er algoritmen til opslagstabellen, der konsekvent genererer spilbare labyrinter i 1982 Atari 2600 -spillet Entombed udelukkende ud fra værdierne for de fem pixels, der støder op til de næste, der skal genereres?
- Hvad er den algoritmiske kompleksitet af det mindste spændende træproblem ? Tilsvarende, hvad er beslutningstræets kompleksitet af MST -problemet? Den optimale algoritme til beregning af MST'er er kendt , men den er afhængig af beslutningstræer, så dens kompleksitet er ukendt.
Naturlige sprogbehandlingsalgoritmer
- Er der nogen perfekt stavelsesalgoritme på det engelske sprog?
- Er der nogen perfekt stammeralgoritme på det engelske sprog?
- Er der nogen perfekt sætning chunking algoritme på det engelske sprog?
- Hvordan kan computere skelne mellem pronomen tvetydighed på det engelske sprog? (Også kendt som Winograd Schema Challenge ).
Programmeringssprogsteori
Andre problemer
- Aanderaa – Karp – Rosenberg formodning
- Černý formodning
- Generaliseret stjernehøjde problem
- Problem med adskillelse af ord
Referencer
eksterne links
- Åbne problemer omkring nøjagtige algoritmer af Gerhard J. Woeginger , Discrete Applied Mathematics 156 (2008) 397–405.
- RTA -listen over åbne problemer - åbne problemer ved omskrivning .
- TLCA -listen over åbne problemer - åbne problemer i områdeskrevet lambda -beregning .