목차
13 처지: EXPTIME, 결정 문제, 계산 복잡도 이론, 튜링 기계, 클레이니 스타, 점근 표기법, 정규 표현식, 집합, 선형 변환, 알고리즘, PSPACE, 1980년, 1차 논리.
- 복잡도 종류
EXPTIME
산 복잡도 이론에서 복잡도 종류 EXPTIME(EXP라고도 한다)은 결정론적 튜링 기계가 \colorBlueO(2^p(n))시간에 풀 수 있는 모든 판정 문제의 집합이.
결정 문제
산 이론에서 결정 문제(decision problem, 판정 문제)란 어떤 형식 체계에서 예-아니오 답이 있는 질문을 말..
계산 복잡도 이론
산 복잡도 이론(Computational complexity theory)은 컴퓨터 과학에서 계산 이론의 분야로, 계산 문제를 푸는 알고리즘을 복잡도에 따라 분류하여 문제의 모임을 구성하는 방법을 연. 이 때 알고리듬의 수행은 실제 컴퓨터가 할 수 있지만, 평가하는 데에는 튜링 기계와 관련이 있는 정량화된 방법을 사용.
튜링 기계
링 기계의 작동 방식을 묘사하는 그림 이론 전산학에서, 튜링 기계()는 긴 테이프에 쓰여있는 여러 가지 기호들을 일정한 규칙에 따라 바꾸는 기계이.
클레이니 스타
이니 스타(Kleene Star)는 문자열이나 문자의 집합에 쓰이는 단항 연산으로, 0개 이상의 임의 원소의 연쇄를 뜻. 스티븐 클레이니가 도입하였으며, 오토마타 이론과 정규 표현식, 형식 문법에서 활용.
점근 표기법
점근 표기법(asymptotic notation)은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이.
정규 표현식
랑색 강조 부분은 다음 정규식을 사용했을 때 매치된 것이다.(?:\.) 2,(?.
집합
9개의 다각형의 집합을 나타낸 오일러 다이어그램 수학에서, 집합(集合)은 명확한 기준에 의하여 주어진 서로 다른 대상들이 모여 이루는 새로운 대상이.
보다 EXPSPACE와 집합
선형 변환
선형대수학에서, 선형 변환(線型變換) 또는 선형 사상(線型寫像) 또는 선형 연산자(線型演算子) 또는 선형 작용소(線型作用素)는 선형 결합을 보존하는, 두 벡터 공간 사이의 함수이.
알고리즘
알고리즘(라틴어, 독일어: Algorithmus)은 수학과 컴퓨터 과학, 언어학 또는 관련 분야에서 어떠한 문제를 해결하기 위한 일련의 절차를 공식화한 형태로 표현한 것을 말. 알고리즘은 연산, 데이터 진행 또는 자동화된 추론을 수행.
PSPACE
산 복잡도 이론에서 PSPACE는 결정론적 튜링 기계나 비결정론적 튜링 기계가 시간은 얼마든지 쓸 수 있고, 공간은 다항 공간만 써서 풀 수 있는 판정 문제들의 집합이.
1980년
1980년은 화요일로 시작하는 윤년이.
1차 논리
1차 논리(一次論理)는 원소에만 한정 기호를 가할 수 있고, 술어에는 한정 기호를 가할 수 없는 술어 논리이.
참고하세요
복잡도 종류
- Co-NP
- Co-NP-완전
- EXPSPACE
- EXPTIME
- L (복잡도)
- MAX-SNP
- NC (복잡도)
- NL (복잡도)
- NP (복잡도)
- NP-난해
- NP-완전
- P (복잡도)
- P-완전
- PH (복잡도)
- PR (복잡도)
- PSPACE
- PSPACE-완전
- R (복잡도)
- RE (복잡도)
- UP (복잡도)
- 다항 시간 근사 해법
- 복잡도 종류
- 복잡도 종류 목록
또한 NEXPSPACE로 알려져 있다.