Како се полиномски верификатор времена може претворити у еквивалентну недетерминистичку Тјурингову машину?
Верификатор полиномског времена може се конвертовати у еквивалентну недетерминистичку Тјурингову машину конструисањем машине која може да погоди сертификат доказа и верификује га у полиномском времену. Ова конверзија је заснована на концепту недетерминистичког израчунавања, који омогућава машини да истовремено истражује све могуће путање.
Да бисмо разумели ову конверзију, хајде да прво дефинишемо шта је полиномски верификатор времена. У теорији сложености рачунара, верификатор полиномског времена је детерминистичка Тјурингова машина која може да провери исправност решења проблема одлуке у полиномском времену. Потребна су два улаза: инстанца проблема и сертификат доказа и одређује да ли је сертификат валидан доказ за дату инстанцу.
Сада, да бисмо конвертовали полиномски верификатор времена у еквивалентну недетерминистичку Тјурингову машину, морамо да размотримо својства недетерминистичког израчунавања. У недетерминистичкој Тјуринг машини, на сваком кораку, машина може бити у више стања и може да пређе у више стања истовремено. Ово омогућава машини да истражује све могуће путеве рачунања паралелно.
Да бисмо конвертовали верификатор, можемо да конструишемо недетерминистичку Тјурингову машину која погађа сертификат доказа и затим симулира верификатор на свим могућим путањама. Ако било која од путања прихвати, онда недетерминистичка машина прихвата. У супротном, одбија.
Хајде да то илуструјемо примером. Претпоставимо да имамо полиномски верификатор времена за проблем бојења графа. Верификатор узима као улаз граф и бојење његових врхова и проверава да ли је бојење валидно тако што проверава да ниједан суседни врх нема исту боју.
Да бисмо овај верификатор претворили у недетерминистичку Тјурингову машину, конструишемо машину која погађа боју и затим симулира верификатор на свим могућим бојама истовремено. Ако било које од боја задовољава ограничења бојења, онда недетерминистичка машина прихвата. У супротном, одбија.
У овом примеру, недетерминистичка машина би погодила бојење додељивањем боја теменима паралелно. Затим би симулирао верификатор на свакој од могућих боја, проверавајући да ли је боја валидна. Ако било која од симулација прихвати, онда недетерминистичка машина прихвата.
Коришћењем ове конверзије, можемо видети да се полиномски верификатор времена може конвертовати у еквивалентну недетерминистичку Тјурингову машину. Ова конверзија нам омогућава да анализирамо сложеност проблема у класи НП (недетерминистичко полиномно време) узимајући у обзир постојање верификатора полиномског времена.
Верификатор полиномског времена може се конвертовати у еквивалентну недетерминистичку Тјурингову машину конструисањем машине која погађа сертификат доказа и верификује га на свим могућим путањама истовремено. Ова конверзија нам омогућава да анализирамо сложеност проблема у класи НП.
Остала недавна питања и одговори у вези Сложеност:
- Зар ПСПАЦЕ класа није једнака класи ЕКСПСПАЦЕ?
- Да ли је П класа сложености подскуп класе ПСПАЦЕ?
- Можемо ли доказати да су Нп и П класа исте проналажењем ефикасног полиномског рјешења за било који НП комплетан проблем на детерминистичком ТМ?
- Може ли класа НП бити једнака класи ЕКСПТИМЕ?
- Постоје ли проблеми у ПСПАЦЕ-у за које не постоји познати НП алгоритам?
- Може ли САТ проблем бити НП потпуни проблем?
- Може ли проблем бити у НП класи сложености ако постоји недетерминистичка Тјурингова машина која ће га решити у полиномском времену
- НП је класа језика који имају верификаторе времена полинома
- Да ли су П и НП заправо иста класа сложености?
- Да ли је сваки језик без контекста у П класи сложености?
Погледајте више питања и одговора у Комплексности