5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

山口人生〜ストリートダンスの連中に絡まれるの巻 Part21

284 :132人目の素数さん:2005/05/14(土) 08:30:46
> 1、正解のみ多項式時間
> と
> 2、任意入力計算が多項式時間
> は同値にはならない。
> 別クラスになる(ように構築できる)から。

この理論でいくと、ソートはクラスPには属しませんね。
指数時間でしか解けないTMを構築できるから。

290 KB
★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.00 2017/10/04 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)