Sta znaci na Engleskom КЛАСА СЛОЖЕНОСТИ - prevod na Енглеском

• complexity class
• complexity classes

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

Односи између класа сложености.
Relationships between complexity classes.

Неколико важних класа сложености је дефинисано у односу на DSPACE.
Several important complexity classes are defined in terms of DSPACE.

Теорема време и просто хијерархије предсрављају основу за већину резултта класа сложености раздвајања.
The time and space hierarchy theorems form the basis for most separation results of complexity classes.

Неколико важних класа сложености може да се дефинише у односу на NSPACE.
Several important complexity classes can be defined in terms of NSPACE.

Блумове аксиоме се могу користити за дефинисање класа сложености без позивања на неки конкретни рачунски модел.
The Blum axioms can be used to define complexity classes without referring to a concrete computational model.

Добро позната класа сложености NP може да се дефинише у терминима NTIME на следећи начин.
The complexity class NP can be defined in terms of NTIME as.

У рачунарској теорији сложености, P позната као PTIME или DTIME( nO( 1)) је једна од фундаменталних класа сложености.
P(complexity) In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is one of the most fundamental complexity classes.

Неколико важних просторних класа сложености су сублинеарне, то јест мање су од величине улаза.
Several important space complexity classes are sublinear, that is, smaller than the size of the input.

PR је класа сложености свих примитивних рекурзивних функција, или еквивалентно- скуп свих формалних језика који се могу определити таквом функцијом.
PR is the complexity class of all primitive recursive functions- or, equivalently, the set of all formal languages that can be decided by such a function.

У теорији рачунарске сложености, класа сложености је скуп проблема повезаних ресурсима заснованим на сложености.
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity..

Претпоставимо да је C класа сложености проблема одлучивања, који су решиви у логаритамском простору на пробабилистичким Тјуринговим машинама које никада не прихватају погрешне улазе, али им је дозвољено да погрешно одбаце исправне улазе у току мање од 1/ 3 времена обраде.
Suppose C is the complexity class of decision problems solvable in logarithmithic space with probabilistic Turing machines that never accept incorrectly but are allowed to reject incorrectly less than 1/3 of the time; this is called one-sided error.

EXPTIME је само једна класа у експоненцијалној хијерархији класа сложености са све сложенијим ораклима или квантификаторима алтернација.
EXPTIME is one class in an exponential hierarchy of complexity classes with increasingly more complex oracles or quantifier alternations.

За сваку функцију f( n), постоји класа сложености SPACE( f( n)), скуп проблема одлучивања који могу да буду решени помоћу детерминистичке Тјурингове машине коришћењем простора O( f( n)).
For each function f(n), there is a complexity class SPACE(f(n)), the set of decision problems that can be solved by a deterministic Turing machine using space O(f(n)).

У рачунарској теорији сложености, NL( Недетерминистички логаритамски простор) класа сложености је која садржи проблеме одлучивости који могу да буду решени помоћу недетерминистичке Тјурингове машине, коришћењем логаритамске величине меморије.
In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space.

У рачунарској теорији сложености, класа сложености NEXPTIME, која се понекад назива NEXP, је скуп проблема одлучивања који могу бити решени помоћу недетерминистичке Тјурингове машине коришћењем 2n O( 1) времена и неограниченог простора.
In computational complexity theory, the complexity class NEXPTIME(sometimes called NEXP) is the set of decision problems that can be solved by a non-deterministic Turing machine using time 2 n O( 1){\displaystyle 2^{ n^{ O( 1)}}}.

У рачунарској теорији сложености, L( позната и као LSPACE или DLOGSPACE) је класа сложености која садржи проблеме одлучивости, који могу да буду решени помоћу детерминистичке Тјурингове машине која користи логаритамску количину меморијског простора.
In computational complexity theory, L(also known as LSPACE or DLOGSPACE) is the complexity class containing decision problems that can be solved by a deterministic Turing machine using a logarithmic amount of writable memory space.

Важне класе сложености.
Important complexity classes.

Многе класе сложености су дефинисане коришћењем појма редукције.
Many complexity classes are defined using the concept of a reduction.

Ова мотивација концепта проблема је тежа за класе сложености.
This motivates the concept of a problem being hard for a complexity class.

Најједноставније класе сложености су дефинисане следећим факторима.
Simpler complexity classes are defined by the following factors.

Друге важне класе сложености укључују BPP, ZPP и RP, које су дефинисане користећи пробабилистичке Тјуринове машине.
Other important complexity classes include BPP, ZPP and RP, which are defined using probabilistic Turing machines.

Било која одговарајућа функција може бити искоришћена за одређивање класе сложености, али само неке класе је вредно изучавати.
Any proper complexity function can be used to define a complexity class, but only certain classes are useful to study.

Најједноставније класе сложености су дефинисане следећим факторима: Тип рачунарских проблема: Најчешће коришћени проблеми су проблеми одлучивања.
Simpler complexity classes are defined by the following factors: The type of computational problem: The most commonly used problems are decision problems.

Мера NSPACE се користи за дефинисање класе сложености проблема чија решења могу да буду одређена помоћу недетерминистичке Тјурингове машине.
The measure NSPACE is used to define the complexity class whose solutions can be determined by a non-deterministic Turing machine.

Један од могућих путева за раздвајање две класе сложености је да се пронађе особина затворења једног, а не другог.
One possible route to separating two complexity classes is to find some closure property possessed by one and not by the other.

За класе сложености дефинисане на овај начин, пожељно је доказати да опуштање услова за( рецимо) рачунање времена заиста дефинише већи скуп проблема.
For the complexity classes defined in this way, it is desirable to prove that relaxing the requirements on(say) computation time indeed defines a bigger set of problems.

Проблем расподеле( L, D) је у класи сложености distNP ако је L у NP и ако је D П-израчунљива.
A distributional problem(L, D) is in the complexity class distNP if L is in NP and D is P-computable.

Многе важне класе сложености могу бити дефинисане помоћу граница времена или простора које користи алгоритам.
Many important complexity classes can be defined by bounding the time or space used by the algorithm.

Међутим, класе сложености се могу дефинисати на основу функцијских проблема( пример је FP), рачунарских проблема( нпр. P), оптимизационих проблема, обећавајућих проблема итд….
However, complexity classes can be defined based on function problems(an example is FP), counting problems(e.g. P), optimization problems, promise problems, etc.

Многе класе сложености се могу окарактерисати као математичка логика која жели да их изрази;
Many complexity classes can be characterized in terms of the mathematical logic needed to express them; see descriptive complexity..