NPとか
なんかここでの会話は怪しい気がするが細かい訂正を書いてる暇がない．
まず「SATは決定問題だから，その解は{x1=T, x2=F, ...}でなくYES/NOですよ」とか...
それを踏まえて，Wikipediaで言うところの
第一に非決定性チューリング機械は「最も幸運な推測機; luckiest possible guesser」であるとする考え方
私はこれ嫌いなんだよね... (and x1 (not x1)) のような答えがNOの決定問題に対してどう「推測」するのか意味不明じゃん？ 「答えがNOなら適当に最初の選択肢を選ぶ」とか反論するなら，じゃあ「最初から答えがYES/NOって分かるなら『各分岐で推測』とかまだるっこしいことは要らないよね」と言わせていただこう．やはり計算のツリーが一番だと思う．
と言うことで，教訓：「理論屋の言葉遣いが留保や仮定や形式的定義の羅列でゴチャゴチャして自分の直感ですっきり受容できないと思えたとき，大抵それにはテクニカルな根拠があるので，がんばって自分の直感の方を修正するしかない」短く言えば「学問に王道なし」
