turing/3.html

<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>&#x795E;&#x8C15;&#x56FE;&#x7075;&#x673A;&#xFF08;Oracle Turing Machine&#xFF09;</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-body vscode-light">
        <h1 id="神谕图灵机oracle-turing-machine">神谕图灵机（Oracle Turing Machine）</h1>
<p>神谕图灵机的提出是为了引出图灵归约和 NP-hard ，可以在<a href="./../doc/tsp.html">货郎问题</a>一节理解图灵归约和神谕图灵机。</p>
<p>OTM 和 <a href="./2.html">DTM</a> 很相似，但比 DTM 多了一个神谕状态，和神谕纸带。</p>
<p>这多出来的神谕状态可以被看做是一个黑盒子函数，用于帮助我们求解某些难以求解的问题。</p>
<p>比如，已知<a href="../doc/tsp.html">货郎判定问题</a>是 NP-hard，那么货郎优化问题的难度应该如何表示？</p>
<p><strong>假设存在一个在多项式时间内解货郎优化问题的算法</strong> A，随后用该算法求出最短路径 L，如果 L大于判定问题，就输出 NO，否则输出 YES。通过这种方法，我们用<strong>货郎优化问题解决了货郎判定问题</strong></p>
<p>在上面的例子中，算法 A 就是<strong>神谕</strong>，以假设货郎优化问题的算法为多项时间为基础，<strong>设计算法并证明货郎判定问题是多项式时间的过程</strong>，被称为<strong>图灵归约</strong>。上述的过程读作将<strong>货郎判定问题图灵归约到货郎优化问题</strong>。</p>
<p>此时，根据<a href="./5.html">图灵归约</a>的定义，货郎判定问题是 NP-hard，因此货郎优化问题也是 NP-hard。</p>
<blockquote>
<p>可以看出，如果货郎优化问题可以在多项式时间内解答，那么货郎判定问题一定可以在多项式时间内解答；但是如果货郎判定问题可以在多项式时间内解答，<strong>根据上述算法</strong>，货郎优化问题不一定可以在多项式时间内解答。（可以根据上述图灵归约认定货郎优化问题比货郎判定问题难）</p>
<p>不过实际上，也可以将货郎优化问题图灵归约到货郎判定问题。这种情况下就可以认为货郎优化问题是 NP等价的。</p>
</blockquote>

    </body>
    </html>