Theoretical Computer Science Asked by Dominic van der Zypen on October 30, 2021

What are examples of problems that are known to be sub-exponential, but

- are known to be non-polynomial, or
- are not known to be polynomial?

**EDIT.** Here is what I mean by sub-exponential (apologies for leaving this open). A function $f:mathbb{N}tomathbb{N}$ is *subexponential* if $$f(n) = 2^{n^{o(1)}}.$$ (Thanks to Emil Jerabek for his help in the comment section below!)

Discrete log in multiplicative groups of finite fields of small characteristic has quasi-polynomial running time. Specifically, for $mathbb{F}_{p^n}^times$ (where inputs have size $log_2(p^n) = nlog_2(p)$) the (expected) running time is $(pn)^{2log_2(n) + O(1)} = 2^{2log_2(p)log_2(n) + O(1) + 2 log_2(n)^2 + O(log_2(n))} = 2^{O(log_2(n)^2)}$

Answered by Mark on October 30, 2021

Problems in $NTIME[f(n)]$ where $f(n)=omega(log n)$ and $f(n)=o(n)$ are not known to be in $DTIME[n^c]$ at any $cgeq1$ while known to be in $DTIME[2^{o(n)}]$.

Conversely there are problems not known to be in $NTIME[f(n)]$ where $f(n)=omega(log n)$ and $f(n)=o(n)$ and also not known to be in $DTIME[n^c]$ at any $cgeq1$ while known to be in $DTIME[2^{o(n)}]$.

Examples of $2$ include factoring and discrete logarithm.

Answered by VS. on October 30, 2021

The General Number Field Sieve is known to be sub-exponential in the size of the input, for example see this quote from the link I just gave:

The running time of the number field sieve is super-polynomial but sub-exponential in the size of the input.

However no polynomial-time algorithm for factoring integers is known (yet).

Answered by user1271772 on October 30, 2021

VC-dimension of set systems is known to be quasipolynomial but not known to be polynomial, with some evidence (based on the strong exponential time hypothesis) that it is not polynomial.

See:

Linial, Nathan, Mansour, Yishay, and Rivest, Ronald L. (1991), “Results on learnability and the Vapnik–Chervonenkis dimension”, Inf. Comput. 90 (1): 33–49.

Manurangsi, Pasin, and Rubinstein, Aviad (2017), “Inapproximability of VC dimension and Littlestone’s dimension”, Proc. 2017 Conf. Learning Theory (COLT 2017), Proceedings of Machine Learning Research 65, pp. 1432–1460.

Papadimitriou, Christos H., and Yannakakis, Mihalis (1996), “On limited nondeterminism and the complexity of the V–C dimension”, J. Comput. Syst. Sci. 53 (2): 161–170.

Answered by David Eppstein on October 30, 2021

Parity games have recently been shown to be solvable in quasipolynomial time: https://doi.org/10.1137/17M1145288

Answered by Hermann Gruber on October 30, 2021

Minimum dominating set in tournaments problem has quasi-polynomial time algorithm (hence sub-exponential). There is no known polynomial time algorithm for it. Tournament dominating set has polynomial-time algorithm if and only if SAT has sub-exponential time algorithm. Therefore, the exponential time hypothesis (ETH) implies that tournament dominating set can not have polynomial time algorithm. Furthermore, ETH implies that tournament dominating set is in $NP$-intermediate.

Answered by Mohammad Al-Turkistany on October 30, 2021

Graph Isomorphism is known to be in quasipolynomial time but not known to be in polynomial time: https://arxiv.org/abs/1512.03547

You can also come up with synthetic problems by the time hierarchy theorem, which essentially states that there are problems at any (deterministic) time complexity but not below: https://en.wikipedia.org/wiki/Time_hierarchy_theorem

Answered by Mahdi Cheraghchi on October 30, 2021

Get help from others!

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

Recent Answers

- haakon.io on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Joshua Engel on Why fry rice before boiling?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP