Zobrazeno 1 - 10
of 55
pro vyhledávání: '"limited nondeterminism"'
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
Salamon, Andr��s Z., Wehar, Michael
We introduce techniques for proving superlinear conditional lower bounds for polynomial time problems. In particular, we show that CircuitSAT for circuits with m gates and log(m) inputs (denoted by log-CircuitSAT) is not decidable in essentially-line
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::57de169e188adc02ac187e322c84870f
Autor:
András Z. Salamon, Michael Wehar
A classic result of Paul, Pippenger, Szemer\'edi and Trotter states that DTIME(n) is strictly contained in NTIME(n). The natural question then arises: could DTIME(t(n)) be contained in NTIME(n) for some superlinear time-constructible function t(n)? I
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::fac7052d8d5bb9a1002c1abb733d9572
http://arxiv.org/abs/2111.02138
http://arxiv.org/abs/2111.02138
Publikováno v:
ACM Transactions on Computation Theory
ACM Transactions on Computation Theory, ACM, 2016, 9 (1), pp.1-34. ⟨10.1145/3013516⟩
ACM Transactions on Computation Theory, 2016, 9 (1), pp.1-34. ⟨10.1145/3013516⟩
ACM Transactions on Computation Theory, ACM, 2016, 9 (1), pp.1-34. ⟨10.1145/3013516⟩
ACM Transactions on Computation Theory, 2016, 9 (1), pp.1-34. ⟨10.1145/3013516⟩
A formulation of Nečiporuk’s lower bound method slightly more inclusive than the usual complexity-measure-specific formulation is presented. Using this general formulation, limitations to lower bounds achievable by the method are obtained for seve
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7cf18065ee7bb264ea3124d24b7bd3dd
https://doi.org/10.1145/3013516
https://doi.org/10.1145/3013516
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
Finkelstein, Jeffrey
Computational complexity theory studies which computational problems can be solved with limited access to resources. The past fifty years have seen a focus on the relationship between intractable problems and efficient algorithms. However, the relati
Externí odkaz:
https://hdl.handle.net/2144/20720
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Publikováno v:
Theoretical Computer Science. 410(37):3447-3460
A generalization of pushdown automata towards regulated nondeterminism is studied. The nondeterminism is governed in such a way that the decision, whether or not a nondeterministic rule is applied, depends on the whole content of the stack. More prec
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::79aea190684bae3a12f7fc710853012d
Publikováno v:
Discrete Applied Mathematics. 156:2035-2049
Dualization of a monotone Boolean function represented by a conjunctive normal form (CNF) is a problem which, in different disguise, is ubiquitous in many areas including Computer Science, Artificial Intelligence, and Game Theory to mention some of t
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::36d409ca9ef5d030336ef3088d3cdc14
https://doi.org/10.1016/j.dam.2007.04.017
https://doi.org/10.1016/j.dam.2007.04.017
Autor:
Andreas Malcher
Publikováno v:
Developments in Language Theory
It is known that deterministic finite automata (DFAs) can be algorithmically minimized, i.e., a DFA M can be converted to an equivalent DFA M′ which has a minimal number of states. The minimization can be done efficiently (in: Z. Kohavi (Ed.), Theo
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8dca2eb72079da6dea9790735b5fcd42
https://doi.org/10.1016/j.tcs.2004.03.070
https://doi.org/10.1016/j.tcs.2004.03.070