[알고리즘] P vs NP

2024. 12. 11. 23:43·자료구조 | 알고리즘

P vs NP 문제 : 컴퓨터가 답이 되는 몇 가지 경우는 빠르게 찾을 수 있지만, 최적의 답을 빠르게 찾을 수는 없는 모든 경우에 대한 문제

 

- P (Deterministic Polynomial time, 결정론적 다항 시간)

  • 다항식 시간복잡도를 가진 알고리즘으로 해결되는 문제 집합 (O(n), O(n²))
  • P 클래스는 입력 크기에 대해 다항 시간 안에 결정론적 순차 기계에서 해결할 수 있는 모든 결정 문제들을 포함

 

- NP (Non-deterministic Polynomial time, 비결정론적 다항 시간)

  • 비결정적 다항식 시간 알고리즘으로 해결되는 문제 집합 (O(n!), O(2^n))
  • NP 알고리즘은 주어진 해에 대해 'Yes'를 확인해야 하므로 결정 문제로 변형
  • NP 클래스는 긍정적인 해답을 주어진 정보로 다항 시간 안에 검증할 수 있는 결정 문제들 또는 비결정론적 기계에서 다항 시간 안에 해답을 찾을 수 있는 결정 문제들을 포함

- NP-complete 

  • 모든 다른 NP 문제를 다항 시간 내에 변환할 수 있는 문제 집합으로, 해결된 답을 다항 시간 내에 변환할 수 있는 문제 집합으로, 해결된 답을 다항 시간 내에 검증할 수 있는 문제들로 구성

- NP-hard

  • NP에 속하는 모든 문제에 대해 polynomial time many one reducible 문제들의 집합

* NP-hard이면서 NP인 문제: NP-complete  (subset sum)

* NP-hard이면서 NP-complete가 아닌 문제 (halting problem)

 

 

'자료구조 | 알고리즘' 카테고리의 다른 글

비트마스크 (BitMask), 비트마스크 문제  (0) 2024.11.04
우선순위 큐 / 힙(heap)  (0) 2024.02.18
리스트 컴프리헨션, 집합 자료형  (0) 2024.02.04
서로소 집합 알고리즘  (0) 2024.02.04
플로이드 워셜 알고리즘  (2) 2024.02.02
'자료구조 | 알고리즘' 카테고리의 다른 글
  • 비트마스크 (BitMask), 비트마스크 문제
  • 우선순위 큐 / 힙(heap)
  • 리스트 컴프리헨션, 집합 자료형
  • 서로소 집합 알고리즘
seulll
seulll
개인 공부 / 정리 블로그입니다
  • seulll
    seulll
    seulll
  • 전체
    오늘
    어제
    • 분류 전체보기 (333) N
      • 코딩테스트 (227) N
        • programmers (python) (156)
        • 백준 (python) (69) N
      • 자료구조 | 알고리즘 (14)
      • 개발 | 프로젝트 (19) N
        • Python (4)
        • Java | Spring (7)
        • Android (4)
        • Unity (3)
        • API (4)
      • CS (15)
        • Network (5)
        • SQL (2)
        • OS (4)
      • 데이터 분석 (14)
      • 기타 (13)
  • 블로그 메뉴

    • 홈
    • 태그
    • 글쓰기
    • 설정
  • 링크

    • GitHub
  • 인기 글

  • 태그

    2 x n 타일링
    야근 지수
    API
    Python
    confusion matrix
    대입 표현식
    모델 성능 평가
    박스플롯
    백엔드
    백엔드 개발자
    Greedy
    바다코끼리
    Boxplot
    티스토리챌린지
    train_test_split
    코딩테스트
    오블완
    웹크롤링
    그리디 알고리즘
    파이썬
    카카오맵
    데이터분석
    asterisk
    오차행렬
    백엔드 개발자 역량
    프렌즈4블록
    kakao map api
    solving environment
    카카오맵 api
    프로그래머스
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
seulll
[알고리즘] P vs NP
상단으로

티스토리툴바