January 11th, 2015

ёжик

Задачи из NP - проверять только «слова» или ещё и «дела»?

Копирую сюда свой пост с dxdy.ru - http://dxdy.ru/post960183.html#p960183

Про класс NP и про NP_primitive.

Меня тут ещё один вопрос озадачил. Вот я построил в прошлом доказательстве (доказательство ли это и доказательство чего - похоже дискуссионный вопрос - о чём скажу) алгоритм AntiMt(), который всегда поступает вопреки алгоритму решения. Да, я там решал спорную задачу (но считаю пока что прав), но могу решать и с вполне конкретным алгоритмом проверки и алгоритм  AntiMt() будет обладать тем же свойством.

Так вот вопрос - а если в теории (а моя задача теперь будет вполне конкретная математическая теория) я аксиоматизирую, чему должен быть равен алгоритм решения Mt когда он разбирается с алгоритмом AntiMt()? Притом аксиоматизирую корректно:

Mt(Aks, «AntiMt()») = knockout

И в составе аксиом Aks будет находится и само это равенство (я это сделаю при помощи диагонализации). Разве это не докажет моментально неполноту алгоритма решения Mt и невозможность, таким образом, свести задачу к задаче класса P?

Я поясню. Эта аксиома вместе с прочими оказывается непротиворечивой, если Mt(Aks, «AntiMt()») действительно выдаст knockout (довольно очевидно, но докажу). Но тогда алгоритм Mt неполный, потому что он ничего не выдает про поведение AntiMt(). В то время как в теории результат для AntiMt() выводится из данной аксиомы.

Разумеется, Mt(Aks, «AntiMt()») может вопреки аксиоме выдать «правильный» прогноз для AntiMt() - соответствующий короткому доказательству из новой аксиомы. Да только этот результат будет неправильным - потому что AntiMt() всегда опровергает предсказания Mt (кроме случая когда Mt ничего не прогнозирует и выдаёт knockout). И сама теория будет противоречивой, разумеется! И вот что интересно. Нам же алгоритм решения Mt нужен для того, чтобы получать решения. Правильные. И если мы получаем то, что не отвечает теории, то мы отвергаем такой алгоритм решения.

Collapse )