Sta znaci na Engleskom EKSPONENCIJALNOG VREMENA - prevod na Енглеском

• exponential time

Примери коришћења Eksponencijalnog vremena на Српском и њихови преводи на Енглески

Hipoteza eksponencijalnog vremena je pretpostavka da za svako k> 2, sk> 0.
The exponential time hypothesis is the conjecture that, for every k> 2, sk> 0.

Ekvivalentno, ako je sk> 0 za bilo koje k> 3, onda je i s3> 0, i hipoteza eksponencijalnog vremena bi bila istinita.
Equivalently, if sk> 0 for any k> 3, then s3> 0 as well, and the exponential time hypothesis would be true.

Hipoteza eksponencijalnog vremena, ako je istinita, podrazumevala bi da je P ≠ NP.
The exponential time hypothesis, if true, would imply that P≠ NP, but it is a stronger statement.

Ekvivalentno, bilo kakvo poboljšanje u ovim vremenima izvršenja bi opovrgnula hipotezu jakog eksponencijalnog vremena.
Equivalently, any improvement on these running times would falsify the strong exponential time hypothesis.

Međutim, ako hipoteza brzog eksponencijalnog vremena nije tačna, i dalje bi bilo moguće za sCNF da bude jednak jedinici.
However, if the strong exponential time hypothesis fails, it would still be possible for sCNF to equal one.

Ako se klike ili nezavisni skupovi logaritamskih veličina mogu naći u polinomijalnom vremenu, hipoteza eksponencijalnog vremena nije tačna.
If cliques or independent sets of logarithmic size could be found in polynomial time, the exponential time hypothesis would be false.

Samim tim, ako je hipoteza eksponencijalnog vremena tačna, mora postojati beskonačno mnogo vrednosti k za koje se sk razlikuje od sk+ 1.
Therefore, if the exponential time hypothesis is true, there must be infinitely many values of k for which sk differs from sk+ 1.

Samim tim, iako pronalaženje klika ili nezavisnih skupova malih veličina najverovatnije nije NP kompletno, hipoteza eksponencijalnog vremena implicira da su ovi problemi nepolinomijalni.
Therefore, even though finding cliques or independent sets of such small size is unlikely to be NP-complete, the exponential time hypothesis implies that these problems are non-polynomial.

Neki izvori definišu hipotezu eksponencijalnog vremena kao malo slabiju izjavu da 3-SAT ne može biti rešen u 2o( n) vremenu..
Some sources define the exponential time hypothesis to be the slightly weaker statement that 3-SAT cannot be solved in time 2o(n).

Takođe je moguće dokazati implikacije u drugom smeru, od neuspeha varijacija hipoteze jakog eksponencijalnog vremena do razdvajanja klasa kompleksnosti.
It is also possible to prove implications in the other direction, from the failure of a variation of the strong exponential time hypothesis to separations of complexity classes.

Ako je hipoteza eksponencijalnog vremena tačna, onda 3-SAT ne bi imao algoritam u polinomijalnom vremenu, što bi značilo da je P različito od NP.
If the exponential time hypothesis is true, then 3-SAT would not have a polynomial time algorithm, and therefore it would follow that P≠ NP.

Postoje NP kompletni problemi za koje poznato najbolje vreme ima formu O( 2nc) za c< 1, i ako bi najbolje moguće vreme izvršavanja za 3-SAT bilo u ovom obliku, onda bi P bilo različito od NP, jer je 2-SAT Np kompletno i ova granica nije polinomijalna, ali bi hipoteza eksponencijalnog vremena bila netačna.
There exist NP-complete problems for which the best known running times have the form O(2nc) for c< 1, and if the best possible running time for 3-SAT were of this form, then P would be unequal to NP(because 3-SAT is NP-complete and this time bound is not polynomial) but the exponential time hypothesis would be false.

Hipoteza eksponencijalnog vremena podrazumeva da mnogi drugi problemi u klasi kompleksnosti SNP nemaju algoritme čije je vreme izvršenja brže od cn za neku konstantu c.
The exponential time hypothesis implies that many other problems in the complexity class SNP do not have algorithms whose running time is faster than cn for some constant c.

Postoji hijerarhija parametrizovanih klasa kompleksnosti nazvanaM hijerarija koja se meša u W hijerarhiju u smislu da, za svako i,M ⊆ W ⊆ M. Hipoteza eksponencijalnog vremena je ekvivalentna tvrdnji daM ≠ FPT, i pitanje da li jeM= W za i> 1 je takođe otvoreno.
There is a hierarchy of parameterized complexity classes called the M-hierarchy that interleaves the W-hierarchy in the sense that, for all i, M⊆ W⊆ M; for instance, the problem of finding a vertex cover of size k log n in an n-vertex graph with parameter k is complete for M. The exponential time hypothesis is equivalent to the statement that M≠ FPT, and the question of whether M= W for i> 1 is also open.

Konkretno, ako je hipoteza jakog eksponencijalnog vremena tačna, onda bi granica optimalnog vremena za pronalaženje nezavisnih skupova na grafu širine w bila( 2- o( 1)) wnO( 1), optimalno vreme za dominirajući problem skupova( 3- o( 1)) wnO( 1) a optimalno vreme za k bojenje je( k- o( 1)) wnO( 1).
In particular, if the strong exponential time hypothesis is true, then the optimal time bound for finding independent sets on graphs of treewidth w is(2- o(1))wnO(1), the optimal time for the dominating set problem is(3- o(1))wnO(1), the optimum time for maximum cut is(2- o(1))wnO(1), and the optimum time for k-coloring is(k- o(1))wnO(1).

U parametrizovanoj teoriji kompleksnosti, jer hipoteza eksponencijalnog vremena implicira da ne postoji algoritam fiksnog parametra za maksimum kliku, takođe implicira da je W ≠ FPT.
In parameterized complexity theory, because the exponential time hypothesis implies that there does not exist a fixed-parameter-tractable algorithm for maximum clique, it also implies that W≠ FPT.

Вишеструка рецурзија, с друге стране, може да захтева експоненцијално време и простор, и важније рекурзивни, не могу да буду замењени итерацијом без експлицитног стека.
Multiple recursion, by contrast, may require exponential time and space, and is more fundamentally recursive, not being able to be replaced by iteration without an explicit stack.

Ипак, општи проблем проналажења оптималног бојења грана је НП-комплетан и најбржим знаним алгоритмима за то је неопходно експоненцијално време.
However, the general problem of finding an optimal edge coloring is NP-hard and the fastest known algorithms for it take exponential time.

Постоје алгоритми полимијалне временске сложености који рачунају оптимално бојење бипартитних графова, и бојење небипартитних простих графова који користе највише Δ+1 боја; ипак, општи проблем проналажења оптималног бојења грана је НП-комплетан и најбржим знаним алгоритмима за то је неопходно експоненцијално време.
There are polynomial time algorithms that construct optimal colorings of bipartite graphs, and colorings of non-bipartite simple graphs that use at most Δ+1 colors; however, the general problem of finding an optimal edge coloring is NP-hard and the fastest known algorithms for it take exponential time.

Čak i kada uspešno završe, analizatori koji koriste rekurzivni spust sa podrškom mogu da zahtevaju eksponencijalno vreme za rad.
Even when they terminate, parsers that use recursive descent with backtracking may require exponential time.

Dragi moji, živimo u eksponencijalnim vremenima!
Dear Educator, we live in exciting times!

Такође је познато да, ако је P= NP, важи и да је EXPTIME= NEXPTIME, класи проблема решивих у експоненцијалном времену на недетерминистичкој Тјуринговој машини.
It is also known that if P= NP, then EXPTIME= NEXPTIME, the class of problems solvable in exponential time by a nondeterministic Turing machine.

Можемо да прођемо кроз сваку могућу групацију( груба сила), али би ово захтевало експоненцијално време у ондосу на број матрица, што је изузетно споро и непрактично за велико n( број матрица).
We could go through each possible parenthesization(brute force), but this would require time exponential in the number of matrices, which is very slow and impractical for large n.

Можемо да прођемо кроз сваку могућу групацију( груба сила), али би ово захтевало експоненцијално време у ондосу на број матрица, што је изузетно споро и непрактично за велико n( број матрица).
Checking each possible parenthesization(brute force) would require a run-time that is exponential in the number of matrices, which is very slow and impractical for large n.

Можемо да прођемо кроз сваку могућу групацију( груба сила), али би ово захтевало експоненцијално време у ондосу на број матрица, што је изузетно споро и непрактично за велико n( број матрица).
We could go through each possible parenthesization(brute force), but this would require time O(2n), which is very slow and impractical for large n.

Пошто ове методе имају експоненцијални раст времена, практична граница од н цифара се постиже веома брзо.
Because these methods also have superpolynomial time growth a practical limit of n digits is reached very quickly.

Ипак, ово је сасвим задовољавајући начин, имајући у виду да чак и најпознатији алгоритми имају експоненцијални раст времена.
Even so, this is a quite satisfactory method, considering that even the best known algorithms have exponential time growth.