Publication View

Proof verification and hardness of approximation problems (1992)

Abstract

We show that every language in NP has a probablistic verifier that checks membership proofs for it using logarithmic number of random bits and by examining a constant number of bits in the proof. If a string is in the language, then there exists a proof such that the verifier accepts with probability 1 (i.e., for every choice of its random string). For strings not in the language, the verifier rejects every provided “proof " with probability at least 1/2. Our result builds upon and improves a recent result of Arora and Safra [6] whose verifiers examine a nonconstant number of bits in the proof (though this number is a very slowly growing function of the input length). As a consequence we prove that no MAX SNP-hard problem has a polynomial time approximation scheme, unless NP=P. The class MAX SNP was defined by Papadimitriou and Yannakakis [82] and hard problems for this class include vertex cover, maximum satisfiability, maximum cut, metric TSP, Steiner trees and shortest superstring. We also improve upon the clique hardness results of Feige, Goldwasser, Lovász, Safra and Szegedy [42], and Arora and Safra [6] and shows that there exists a positive ɛ such that approximating the maximum clique size in an N-vertex graph to within a factor of N ɛ is NP-hard. 1

Publication details

Download	http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.145.4652
Source	http://www.cs.umd.edu/~gasarch/pcp/ALMSS.pdf
Contributors	CiteSeerX
Repository	CiteSeerX - Scientific Literature Digital Library and Search Engine (United States)
Type	text
Language	English
Relation	10.1.1.3.9509, 10.1.1.16.183, 10.1.1.130.9311, 10.1.1.124.9739, 10.1.1.38.2537, 10.1.1.26.4807, 10.1.1.128.9251, 10.1.1.19.8428, 10.1.1.17.5556, 10.1.1.42.5832, 10.1.1.10.6494, 10.1.1.49.9648, 10.1.1.47.5344, 10.1.1.36.82, 10.1.1.36.1059, 10.1.1.44.1065, 10.1.1.11.8391, 10.1.1.104.8371, 10.1.1.145.2644, 10.1.1.25.4607, 10.1.1.42.5554, 10.1.1.22.8090, 10.1.1.53.5068, 10.1.1.53.6739, 10.1.1.36.5857, 10.1.1.51.832, 10.1.1.52.8469, 10.1.1.41.2768, 10.1.1.25.2686, 10.1.1.18.3969, 10.1.1.35.7924, 10.1.1.46.6267, 10.1.1.48.8269, 10.1.1.16.3955, 10.1.1.3.9509, 10.1.1.35.8576, 10.1.1.17.5556, 10.1.1.35.5192, 10.1.1.34.6277, 10.1.1.22.2728, 10.1.1.104.8371, 10.1.1.51.3217, 10.1.1.145.2644, 10.1.1.42.5554, 10.1.1.3.583, 10.1.1.6.2885, 10.1.1.41.2697, 10.1.1.22.8090, 10.1.1.17.5821, 10.1.1.41.1165, 10.1.1.13.6534, 10.1.1.3.5089, 10.1.1.45.7862, 10.1.1.36.5857, 10.1.1.40.2892, 10.1.1.43.9283, 10.1.1.44.6312, 10.1.1.49.572, 10.1.1.41.7653, 10.1.1.17.467, 10.1.1.49.6583, 10.1.1.13.6863, 10.1.1.29.8482, 10.1.1.40.1531, 10.1.1.47.2776, 10.1.1.11.2874, 10.1.1.23.4219, 10.1.1.11.1195, 10.1.1.132.2721, 10.1.1.30.362, 10.1.1.36.746, 10.1.1.67.7623, 10.1.1.104.2928, 10.1.1.47.6404, 10.1.1.29.2006, 10.1.1.45.838, 10.1.1.43.9811, 10.1.1.3.175, 10.1.1.35.7924, 10.1.1.3.7599, 10.1.1.40.27, 10.1.1.136.3918, 10.1.1.116.5053, 10.1.1.47.5461, 10.1.1.46.2494, 10.1.1.46.6267, 10.1.1.36.3467, 10.1.1.8.5883, 10.1.1.53.6336, 10.1.1.127.4414, 10.1.1.34.6920, 10.1.1.53.5405, 10.1.1.118.5507, 10.1.1.23.9515, 10.1.1.20.3439, 10.1.1.33.1719, 10.1.1.130.1992, 10.1.1.41.9156, 10.1.1.49.6489, 10.1.1.50.4174, 10.1.1.140.9589, 10.1.1.40.287, 10.1.1.32.2996, 10.1.1.32.8685, 10.1.1.41.2723, 10.1.1.24.3354, 10.1.1.25.4606, 10.1.1.47.9285, 10.1.1.16.2288, 10.1.1.127.2880, 10.1.1.32.5434, 10.1.1.112.8906, 10.1.1.122.337, 10.1.1.17.2564, 10.1.1.49.6305, 10.1.1.35.985, 10.1.1.144.993, 10.1.1.123.9401, 10.1.1.121.7157, 10.1.1.50.2028, 10.1.1.39.717, 10.1.1.10.1339, 10.1.1.131.5136, 10.1.1.41.2031, 10.1.1.26.4792, 10.1.1.3.8197, 10.1.1.101.8860, 10.1.1.28.181, 10.1.1.54.7823, 10.1.1.15.5420, 10.1.1.35.6439, 10.1.1.118.2587, 10.1.1.72.561, 10.1.1.127.6948, 10.1.1.43.7935, 10.1.1.44.7150, 10.1.1.12.4807, 10.1.1.100.439, 10.1.1.132.5340, 10.1.1.36.2958, 10.1.1.51.7169, 10.1.1.52.6097, 10.1.1.36.4893, 10.1.1.47.6435, 10.1.1.6.7983, 10.1.1.54.4375, 10.1.1.30.8418, 10.1.1.102.6948, 10.1.1.42.4461, 10.1.1.52.3835, 10.1.1.52.6128, 10.1.1.21.4107, 10.1.1.3.3628, 10.1.1.34.7941, 10.1.1.46.8127, 10.1.1.49.9535, 10.1.1.12.3920, 10.1.1.124.1644, 10.1.1.25.4259, 10.1.1.45.3754, 10.1.1.81.5074, 10.1.1.84.5564, 10.1.1.85.8775, 10.1.1.119.3118, 10.1.1.137.9478, 10.1.1.51.8549, 10.1.1.42.7609, 10.1.1.36.846, 10.1.1.45.1646, 10.1.1.11.2507, 10.1.1.108.8875, 10.1.1.41.2153, 10.1.1.64.4316, 10.1.1.115.3589, 10.1.1.112.6895, 10.1.1.15.9970, 10.1.1.29.1568, 10.1.1.54.2654, 10.1.1.56.6709, 10.1.1.136.3008, 10.1.1.35.6463, 10.1.1.13.8400, 10.1.1.6.3939, 10.1.1.105.8998, 10.1.1.108.5657, 10.1.1.42.9114, 10.1.1.51.4071, 10.1.1.8.1747, 10.1.1.63.3277, 10.1.1.114.3402, 10.1.1.52.495, 10.1.1.23.1086, 10.1.1.41.70, 10.1.1.26.8607, 10.1.1.31.3510, 10.1.1.56.6165, 10.1.1.40.7690, 10.1.1.30.8848, 10.1.1.23.9726, 10.1.1.21.362, 10.1.1.12.9149, 10.1.1.24.3503, 10.1.1.27.3837, 10.1.1.44.4698, 10.1.1.46.4662, 10.1.1.51.8163, 10.1.1.53.4042, 10.1.1.65.2089, 10.1.1.127.1477, 10.1.1.122.7447, 10.1.1.125.7028, 10.1.1.46.5138, 10.1.1.36.8514, 10.1.1.10.8952, 10.1.1.26.7915, 10.1.1.117.9337, 10.1.1.47.4000, 10.1.1.65.1429, 10.1.1.13.3900, 10.1.1.126.1501, 10.1.1.111.8694, 10.1.1.117.3367, 10.1.1.39.8344, 10.1.1.42.6790, 10.1.1.31.64, 10.1.1.46.4434, 10.1.1.46.80, 10.1.1.52.7869, 10.1.1.53.5146, 10.1.1.56.9394, 10.1.1.119.4089, 10.1.1.78.8272, 10.1.1.87.6528, 10.1.1.93.4406, 10.1.1.117.9270, 10.1.1.20.7088, 10.1.1.54.9740, 10.1.1.51.6866, 10.1.1.34.1159, 10.1.1.25.6298, 10.1.1.31.6878, 10.1.1.26.4402, 10.1.1.2.9055, 10.1.1.15.9179, 10.1.1.32.4931, 10.1.1.139.7750, 10.1.1.104.7625, 10.1.1.22.3613, 10.1.1.37.8988, 10.1.1.5.6240, 10.1.1.52.5685, 10.1.1.57.4896, 10.1.1.63.553, 10.1.1.10.4778, 10.1.1.113.7922, 10.1.1.42.5225, 10.1.1.78.1470, 10.1.1.136.6779, 10.1.1.85.487, 10.1.1.88.4690, 10.1.1.88.790, 10.1.1.89.4377, 10.1.1.95.80, 10.1.1.125.371, 10.1.1.98.3736, 10.1.1.110.4892, 10.1.1.113.907, 10.1.1.114.3324, 10.1.1.117.8848, 10.1.1.118.8354, 10.1.1.126.3783, 10.1.1.51.1560, 10.1.1.135.7940, 10.1.1.135.8202, 10.1.1.49.3132, 10.1.1.55.8170, 10.1.1.32.6486, 10.1.1.54.3068, 10.1.1.25.7866, 10.1.1.19.3790, 10.1.1.40.5402, 10.1.1.36.1163, 10.1.1.36.2925, 10.1.1.31.7518, 10.1.1.25.7292, 10.1.1.101.7613, 10.1.1.102.136, 10.1.1.102.1910, 10.1.1.103.9462, 10.1.1.104.3304, 10.1.1.118.7867, 10.1.1.104.6844, 10.1.1.104.6879, 10.1.1.105.1706, 10.1.1.106.7691, 10.1.1.106.7995, 10.1.1.106.827, 10.1.1.107.8008, 10.1.1.108.3460, 10.1.1.108.9427, 10.1.1.109.6057, 10.1.1.17.8460, 10.1.1.21.3869, 10.1.1.22.450, 10.1.1.129.360, 10.1.1.27.7984, 10.1.1.28.9267, 10.1.1.3.192, 10.1.1.33.1789, 10.1.1.4.9972, 10.1.1.48.8909, 10.1.1.50.5872, 10.1.1.52.6753, 10.1.1.53.3137, 10.1.1.54.7667, 10.1.1.56.364, 10.1.1.60.7228, 10.1.1.62.1789, 10.1.1.128.9483, 10.1.1.63.2604, 10.1.1.63.5261, 10.1.1.64.4038, 10.1.1.64.6311, 10.1.1.65.3377, 10.1.1.65.3882, 10.1.1.65.4981, 10.1.1.132.9162, 10.1.1.65.96, 10.1.1.66.3493, 10.1.1.66.6033, 10.1.1.66.6349, 10.1.1.108.3210, 10.1.1.68.7055, 10.1.1.68.9376, 10.1.1.69.3787, 10.1.1.70.4213, 10.1.1.70.5477, 10.1.1.70.9469, 10.1.1.71.3170, 10.1.1.11.4646, 10.1.1.72.487, 10.1.1.104.8663, 10.1.1.73.2854, 10.1.1.73.7214, 10.1.1.74.4071, 10.1.1.74.9141, 10.1.1.75.7022, 10.1.1.75.7698, 10.1.1.75.9416, 10.1.1.67.3700, 10.1.1.76.8392, 10.1.1.76.8711, 10.1.1.77.4296, 10.1.1.78.8802, 10.1.1.79.4067, 10.1.1.79.6520, 10.1.1.79.8994, 10.1.1.79.9809, 10.1.1.80.2254, 10.1.1.80.3686, 10.1.1.80.8756, 10.1.1.80.8976, 10.1.1.81.2517, 10.1.1.83.1453, 10.1.1.83.4346, 10.1.1.83.7813, 10.1.1.84.2851, 10.1.1.84.5698, 10.1.1.85.4732, 10.1.1.85.7217, 10.1.1.86.1577, 10.1.1.86.3659, 10.1.1.86.8046, 10.1.1.87.7737, 10.1.1.89.2203, 10.1.1.89.4736, 10.1.1.89.8504, 10.1.1.90.2816, 10.1.1.90.9133, 10.1.1.128.3219, 10.1.1.129.6727, 10.1.1.91.8119, 10.1.1.91.9955, 10.1.1.92.2832, 10.1.1.92.3276, 10.1.1.92.4078, 10.1.1.92.8878, 10.1.1.92.9513, 10.1.1.93.4328, 10.1.1.93.5296, 10.1.1.132.1832, 10.1.1.93.9352, 10.1.1.77.5123, 10.1.1.94.3228, 10.1.1.94.4522, 10.1.1.94.533, 10.1.1.95.830, 10.1.1.96.4533, 10.1.1.96.7010, 10.1.1.96.9410, 10.1.1.96.9889, 10.1.1.98.299, 10.1.1.99.528, 10.1.1.110.2530, 10.1.1.110.3448, 10.1.1.110.3769, 10.1.1.110.4779, 10.1.1.110.8016, 10.1.1.111.6885, 10.1.1.112.2851, 10.1.1.112.4589, 10.1.1.112.5604, 10.1.1.112.5732, 10.1.1.112.9742, 10.1.1.113.2407, 10.1.1.113.4340, 10.1.1.113.6086, 10.1.1.113.7543, 10.1.1.114.9645, 10.1.1.115.4147, 10.1.1.115.7713, 10.1.1.115.8902, 10.1.1.116.2692, 10.1.1.116.7115, 10.1.1.116.8005, 10.1.1.116.9359, 10.1.1.117.1078, 10.1.1.118.3590, 10.1.1.118.4864, 10.1.1.119.2849, 10.1.1.120.462, 10.1.1.120.5715, 10.1.1.120.7689, 10.1.1.120.9175, 10.1.1.121.3865, 10.1.1.121.3992, 10.1.1.121.4225, 10.1.1.123.854, 10.1.1.123.1837, 10.1.1.123.2971, 10.1.1.123.4547, 10.1.1.123.4748, 10.1.1.124.7769, 10.1.1.125.4484, 10.1.1.91.2735, 10.1.1.127.2188, 10.1.1.128.5627, 10.1.1.128.9529, 10.1.1.129.128, 10.1.1.129.2223, 10.1.1.130.1032, 10.1.1.130.7151, 10.1.1.131.6990, 10.1.1.131.7404, 10.1.1.131.8196, 10.1.1.131.8359, 10.1.1.132.9048, 10.1.1.134.2885, 10.1.1.134.9822, 10.1.1.135.7066, 10.1.1.136.4925, 10.1.1.136.7760, 10.1.1.137.5348, 10.1.1.138.8507, 10.1.1.16.9869, 10.1.1.131.4875, 10.1.1.117.7571, 10.1.1.139.5686, 10.1.1.44.5330, 10.1.1.47.6394, 10.1.1.52.2294, 10.1.1.53.3614, 10.1.1.53.5578, 10.1.1.53.6170, 10.1.1.54.2261, 10.1.1.51.8700, 10.1.1.52.576, 10.1.1.48.2635, 10.1.1.50.110, 10.1.1.38.6878, 10.1.1.39.3626, 10.1.1.39.8088, 10.1.1.39.8856, 10.1.1.33.907, 10.1.1.40.9697, 10.1.1.41.230, 10.1.1.41.4590, 10.1.1.43.2631, 10.1.1.35.2005, 10.1.1.35.4540, 10.1.1.35.9226, 10.1.1.25.9270, 10.1.1.36.595, 10.1.1.37.4317, 10.1.1.37.5733, 10.1.1.37.6984, 10.1.1.37.7606, 10.1.1.37.7640, 10.1.1.31.5526, 10.1.1.33.1351, 10.1.1.33.3163, 10.1.1.22.2417, 10.1.1.25.9385, 10.1.1.27.3433, 10.1.1.27.6241, 10.1.1.22.2329, 10.1.1.23.2295, 10.1.1.8.7162, 10.1.1.11.927, 10.1.1.3.1515, 10.1.1.3.6804, 10.1.1.4.256, 10.1.1.4.9656, 10.1.1.5.1990, 10.1.1.58.8777, 10.1.1.59.3803, 10.1.1.61.1348, 10.1.1.140.1376, 10.1.1.140.2111, 10.1.1.141.1091, 10.1.1.141.6088, 10.1.1.142.4153, 10.1.1.142.4308, 10.1.1.141.3881, 10.1.1.144.2940, 10.1.1.141.6300, 10.1.1.145.4523