Не кинокритик. Не палеонтолог. (plakhov) wrote,
Не кинокритик. Не палеонтолог.
plakhov

Category:

Две задачи (научное)

1. Найти конечный автомат минимального размера, работающий в точности так же, как данный
2. Найти конечный автомат минимального размера, корректно работающий на заданном множестве строк 

Различие, на первый взгляд, небольшое. Например потому, что какой-нибудь конечный автомат, корректно работающий на заданном множестве строк, строится элементарно. Тонкость состоит в том, что все такие автоматы работают одинаково, вообще говоря, только на этом множестве строк, так что тем самым к задаче 1 все не сводится.

На самом деле первая задача относительно проста, ее решение за O(n2) изложено, например, здесь. Оно выглядит почти тривиальным (правда, только потому, что опирается на теорему Myhill-Nerode, доказательство которой опушено из соображений милосердия к читателю). И существует даже решение за O(n logn).

А вот любой быстрый метод решения второй задачи, по моим и не только моим подозрениям, довольно быстро привел бы к созданию strong AI. К сожалению, она NP-полна.

Tags: 2017, math
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 6 comments