title: Result Verification Algorithms for Optimization Problems.
creator: Gupta, H.
subject: Data Mining
description: In this article we discuss the design of result verification algorithms for optimization problems. In particular, we design time-optimal result verification algorithms which verify the solution of all-pairs shortest paths, maximum-flow in a network, and matching problems. We prove that polynomial-time verification algorithms for NP-complete problems do not exist exist, unless P = NP. Result verification problems for most of the NP-hard problems are not believed to be in NP. W e also consider verification algorithms for approximation algorithms for NP-complete and NP-hard problems.
publisher: Stanford
date: 1995
type: Techreport
type: NonPeerReviewed
format: application/pdf
identifier: http://ilpubs.stanford.edu:8090/99/1/1995-31.pdf
identifier: Gupta, H. (1995) Result Verification Algorithms for Optimization Problems. Technical Report. Stanford. (Publication Note: UIUC, 1995.)
relation: http://ilpubs.stanford.edu:8090/99/
</div><div class="naked_ctrl">
<form action="/index.cgi/contrast" method="get" name="gate">
<p><a href="http://altstyle.alfasado.net">AltStyle</a> によって変換されたページ <a href="http://ilpubs.stanford.edu:8090/cgi/export/99/DC/ilprints-eprint-99.txt">(-&gt;オリジナル)</a>
/ <label>アドレス: <input type="text" name="naked_post_url" value="http://ilpubs.stanford.edu:8090/cgi/export/99/DC/ilprints-eprint-99.txt" size="22" /></label> <label>モード: <select name="naked_post_mode">
<option value="default">デフォルト</option>
<option value="speech">音声ブラウザ</option>
<option value="ruby">ルビ付き</option>
<option value="contrast" selected="selected">配色反転</option>
<option value="larger-text">文字拡大</option>
<option value="mobile">モバイル</option>
</select>
<input type="submit" value="表示" />
</p>
</form>
</div>