다항 시간 oor Engels

다항 시간

Vertalings in die woordeboek Koreaans - Engels

polynomial time

adjective noun

voorbeelde

실제로 다항 시간 기계는 PH에 속한 어떤 문제라도 #P 질의 하나만으로 풀어낼 수 있다.
In fact, the polynomial-time machine only needs to make one ♯P query to solve any problem in PH.

일부 문맥에서는, 특히 최적화의 경우, 강력한 다항 시간과 약한 다항 시간 알고리즘 사이에 차별점이 존재한다.
In some contexts, especially in optimization, one differentiates between strongly polynomial time and weakly polynomial time algorithms.

약한 다항시간은 유사 다항 시간과 헷갈려서는 안된다.
Time-reversibility should not be confused with stationarity.

몇 가지 중요한 다항 시간이 사용되어 정의된 클래스들은 다음과 같다.
Some important classes defined using polynomial time are the following.

Cobham 논제는 다항 시간이 "추적 가능한", "실현 가능한", "효율적인" 또는 "빠른" 과 같은 동의어를 갖는다고 언급한다.
Cobham's thesis states that polynomial time is a synonym for "tractable", "feasible", "efficient", or "fast".

비잔틴 장애를 허용하는 다항 시간 이진 합의 프로토콜의 예로는 Garay와 Berman에 의해 제안된 Phase King 알고리즘이 있다.
An example of a polynomial time binary consensus protocol that tolerates Byzantine failures is the Phase King algorithm by Garay and Berman.

흔히 NP를 이렇게 다시 형식화한다: 어떤 언어가 NP라는 것과 답이 주어질 때 결정론적 기계로 다항시간에 검증할 수 있다는 것은 동치이다.
A common reformulation of NP states that a language is in NP if and only if a given answer can be verified by a deterministic machine in polynomial time.

비슷하게, 주어진 답이 다항 시간에 검증될 수 있고, 검증 기계가 문제 인스턴스마다 답변을 최대 한 개만 받아들이면, 그 언어는 UP이다.
Similarly, a language is in UP if a given answer can be verified in polynomial time, and the verifier machine only accepts at most one answer for each problem instance.

토다 정리(Toda's theorem, (일본어: 戸田誠之助 도다 세이노스케)의 이름을 땄다)에서 나오는 결론 중 하나는, #P 신탁이 있는 다항 시간 기계(P#P)는 PH에 속하는 모든 문제를 풀 수 있다는 것이다.
One consequence of Toda's theorem is that a polynomial-time machine with a ♯P oracle (P♯P) can solve all problems in PH, the entire polynomial hierarchy.

잠시 시간을 내서 다항식을 어떻게 더하고 빼는지에 대해 조금 더 직접적으로 이야기 합시다.
Let's start out by comparing what the difference is between subtracting polynomials and adding polynomials.

다항 시간의 개념은 계산 복잡도 이론에서 여러가지 복잡도 클래스로 연결된다.
The concept of polynomial time leads to several complexity classes in computational complexity theory.

초다항 시간을 필요로하는 알고리즘은 복잡도 클래스 P밖에 놓인다.
An algorithm that requires superpolynomial time lies outside the complexity class P .

만약 두 번째의 요구사항이 충족되지 않으면, 다항시간 알고리즘화의 가능성은 더이상 만족하지 않는다.
If the second of the above requirement is not met, then this is not true anymore.

후자의 관측으로 인해, 강력한 다항 시간에서 이 알고리즘은 작동할 수 없다.
Due to the latter observation, the algorithm does not run in strongly polynomial time.

강력한 다항시간은 계산의 산술 모델에서 정의된다.
Strongly polynomial time is defined in the arithmetic model of computation.

그래프에서의 최대 매칭은 다항 시간동안 찾을 수 있다.
Maximum matchings in graphs can be found in polynomial time.

일부 문맥에서는, 특히 최적화의 경우, 강력한 다항 시간 과 약한 다항 시간 알고리즘 사이에 차별점이 존재한다.
In some contexts, especially in optimization , one differentiates between strongly polynomial time and weakly polynomial time algorithms.

모든 주어진 추상 머신은 해당 머신에 대해 다항 시간동안 해결할 수 있는 문제에 해당하는 복잡도 클래스를 갖는다.
Any given abstract machine will have a complexity class corresponding to the problems which can be solved in polynomial time on that machine.

서브-지수 시간이라는 용어는 어떤 알고리즘의 수행시간이 다항시간보다 빠르지만 현저히 지수시간 보다는 작게 증가하는 것을 표현하는데 사용한다.
The term sub-exponential time is used to express that the running time of some algorithm may grow faster than any polynomial but is still significantly smaller than an exponential.

복잡도 이론에서, 미해결 문제인 P vs. NP문제는 NP문제 모두가 다항 시간 알고리즘인지의 여부를 묻는다.
In complexity theory, the unsolved P versus NP problem asks if all problems in NP have polynomial-time algorithms.

예를 들면, 크기 n 의 입력값에 대해 2n 단계 실행되는 알고리즘은 초다항 시간을 요구한다. (좀 더 정확히 말하자면, 지수 시간이다.)
For example, an algorithm that runs for 2n steps on an input of size n requires superpolynomial time (more specifically, exponential time).

그러므로 튜링 머신에서 다항시간에 이 계산의 결과값을 도출해내는 것은 불가능하지만, 다항 시간을 갖는 많은 산술 연산을 가지고 이것을 계산하는 것은 가능하다.
Hence, it is not possible to carry out this computation in polynomial time on a Turing machine, but it is possible to compute it by polynomially many arithmetic operations.

위와 같은 특성을 가진 모든 알고리즘들은 튜링 머신에서 산술 연산을 수행하는 적합한 알고리즘을 사용해 산술 연산을 교체하는 것으로 다항시간 알고리즘화 할 수 있다.
Any algorithm with these two properties can be converted to a polynomial time algorithm by replacing the arithmetic operations by suitable algorithms for performing the arithmetic operations on a Turing machine .

이 산술 모델에서 기본 산술 연산은 피연산자의 크기에 상관없이 수행하는데 단위 시간 단계가 소요된다. 알고리즘은 아래와 같은 경우, 강력한 다항 시간에 수행된다고 할 수 있다.
In this model of computation the basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) take a unit time step to perform, regardless of the sizes of the operands.

이런 경우, 이 환원은 문제 B가 NP-난제임을 증명할 수 없다; 이 환원은 만약 3SAT에 대한 준-다항 시간 알고리즘이 없다면, 단지 B에 부합하는 다항시간 알고리즘이 없다는 것만을 보여줄 수 있다.
In that case, this reduction does not prove that problem B is NP-hard; this reduction only shows that there is no polynomial time algorithm for B unless there is a quasi-polynomial time algorithm for 3SAT (and thus all of NP ).