실제 문제의 크기 에 대해 지수 알고리즘이 가장 잘 알려진 다항식 시간 대응보다 훨씬 빠르게 실행되는 모든 문제 (바람직하게는 다소 잘 알려진)를 알고 있습니까 ?
예를 들어, 문제의 실제 크기가 이고 두 개의 알려진 알고리즘이 있다고 가정합니다 . 하나는 2 n 이고 다른 하나는 상수 c에 대해 n c 입니다 . 분명히 어떤 위해 C > 15 , 지수 알고리즘이 바람직하다.
n=1002n
nc
c
c>15
* 실제 크기는 실제 세계에서 일반적으로 발견되는 것을 의미한다고 생각합니다. 네트워크의 열차 수와 같습니다.
답변
선형 프로그래밍을위한 심플 렉스 알고리즘은 어떻습니까? 많은 경우 에 실제로 사용 됩니다.
추가하기 위해 편집 : 나는 실제 크기의 적대적 인스턴스 에서 더 빨리 실행되는 것이 아니라 실제 인스턴스 / 배포 에서 효율적으로 실행되는 “최악의 지수 알고리즘”이라고 생각합니다 .
답변
공지 빠른 알고리즘 그래프는 knotless 임베딩되어 있는지 여부를 식별하는 문제에 대한 밀러와 나 이미로 인해, 시간 지수이다. 로버트슨 모어 이론은 있다는 것을 말한다 이 문제의 알고리즘; 그러나이를 기록하려면 매듭없는 임베딩을위한 금지 된 미성년자 목록을 알아야합니다. 그러나이 목록을 알고 있더라도 250 개 이상의 금지 된 미성년자가 있고 그 중 일부는 상당히 큰 합리적인 크기의 그래프에 대해 지수 시간 알고리즘이 훨씬 빠릅니다 .
O(n3)