Должны ли эксперты в TCS брать деньги, чтобы прочитать доказательства того, что P! = NP?

Общеизвестно, что есть множество любителей, в том числе и я, которые заинтересованы в проблеме P против NP. Есть также много любителей, в том числе и я, которые пытались решить проблему.

Одна из проблем, от которой, по моему мнению, страдает сообщество TCS, - это относительно высокое отношение заинтересованного любителя к эксперту; это приводит к тому, что эксперты завалены доказательствами, что P! = NP, и я читал, что они расстроены и поражены, вполне понятно, этой ситуацией. Одед Голдрайх написал по этому вопросу и указал свой отказ проверить доказательства.

В то же время, говоря с точки зрения любителя, я могу утверждать, что есть немного вещей, более расстраивающих для энтузиастов TCS, не являющихся экспертами, любого уровня способностей, чем создание доказательства, которое кажется правильным, но при этом не хватает и того, и другого. способность найти ошибку в доказательстве самостоятельно и способность общаться с любым, кто может обнаружить ошибки в вашем доказательстве. Недавно Р.Дж. Липтон писал о проблеме любителей, которые пытаются воспринимать всерьез.

У меня есть предложение по решению этой проблемы, и мой вопрос заключается в том, считают ли другие это обоснованным или есть проблемы с ним.

Я думаю, что эксперты должны взимать значительную, но разумную сумму денег (скажем, 200–300 долларов США) в обмен на согласие подробно прочитать доказательства и найти в них конкретные ошибки. Это позволит выполнить три вещи:

1. У любителей был бы ясный способ оценить свои доказательства и принять всерьез.
2. Эксперты получат компенсацию за потраченное время и энергию.
3. При проверке доказательств будет значительно дорого обходиться то, что количество представляемых любителями доказательств резко сократится.

Опять же, мой вопрос, является ли это разумным предложением. Очевидно, у меня нет возможности заставить экспертов принять то, что я предлагаю; однако я надеюсь, что эксперты прочитают то, что я написал, и решат, что это разумно.

Позвольте мне ответить на ваше предложение встречным предложением: почему бы вам не попытаться создать бизнес, выступая в качестве посредника между любителями и экспертами? Любители платят за оценку своих доказательств. Вы находите эксперта и платите ему, чтобы он оценил доказательства, взяв часть денег за роль посредника. Попытка запустить такой бизнес - самый надежный способ выяснить, является ли ваша идея осуществимой.

У меня есть «реальный опыт» в этой зарождающейся индустрии (и нет, я не говорю о своем предложении Deolalikar за 200 000 долларов :-))

В январе разработчик программного обеспечения написал мне по электронной почте, что у него есть попытка доказательства P ≠ NP, и, хотя он был почти уверен, что произошла ошибка, он не смог ее найти. Он спросил, знаю ли я аспирантов, которые захотят найти для него ошибку в обмен на несколько сотен долларов.

Чтобы дать вам некоторый контекст: я получаю подтверждение либо P P NP, либо P = NP в моем почтовом ящике примерно раз в месяц. Многие из этих писем идут в длинный список теоретиков сложности (Cook, Karp, Fortnow, Sipser ...); они часто включают религиозные или метафизические размышления, а также мрачные намеки на академические заговоры. (В одном случае были графические угрозы смерти против меня, которые привели к тому, что я связался с полицией.) Практически никто из них не признал никакой вероятности того, что доказательство могло быть неверным или что автор мог неправильно понять вопрос. И когда, вернувшись в аспирантуру, я попытался переписываться с авторами, я обнаружил, что все они являются горячими сторонниками принципа Черчилля «никогда, никогда, никогда, никогда не сдавайся».

Так что просьба разработчика программного обеспечения действительно впечатлила меня! Это был первый раз, когда я видел доказательство P ≠ NP, сопровождаемое таким уровнем самосознания - как о навязывании времени людям, так и (что более важно) о вероятности ошибки. Как это случилось, мой аспирант Майкл Форбс прислал автору прекрасный подробный отчет, объясняющий проблемы его подхода; Автор поблагодарил Майкла и (думаю! :-)) заплатил, как и обещал.

Так что да: для любителей, которые хотят, чтобы кто-то изучил их доказательства P против NP (или аналогичную работу), я думаю, что платить аспиранту несколько сотен долларов - отличный способ. (Обратите внимание, что аспиранты являются гораздо лучшим выбором, чем профессора: они не только обладают большей энергией и энтузиазмом для таких вещей, но и нуждаются в большем количестве денег.) Я хотел бы, чтобы больше любителей воспользовались этим вариантом.

В течение нескольких месяцев в конце моего старшего года обучения в колледже и в начале моего первого года обучения в аспирантуре я зарабатывал 60 долларов в час, исправляя неверные доказательства любителя последней теоремы Ферма. В этом случае человек был академиком в другой области, поэтому у него было разумное понимание ценности времени эксперта. Это был хороший опыт, я заработал тысячу долларов в то время, когда у меня не было других хороших источников дохода, и он узнал об ошибках, допущенных им в нескольких проектах.

Я думаю, что для людей, которые прилагают искренние усилия и которые готовы платить хорошие деньги, не должно быть трудно найти квалифицированных студентов или молодых аспирантов, которым нужны деньги.

Одна проблема, которую я вижу с вашим предложением, состоит в том, что большинство не доказательств P против NP даже не являются ложными. Другими словами, они, как правило, страдают от ошибки определения или спецификации, что делает невозможным их проверку на истинность или на ложность. Я отсылаю вас к моей (бесстыдной саморекламе!) Карикатуре на типичное взаимодействие между экспертами и любителями P против NP : трудно понять, как внесение денег в эту дискуссию улучшит ее.

ps вышеупомянутая карикатура основана на просмотре железнодорожных кораблекрушений на comp.theory: Тимоти Чоу мог бы сказать больше об этом, так как он часто терпеливо пытается привлечь таких людей.

Я помню, как ходил на языковую конференцию в 1985 году, где состоялся следующий обмен:

Докладчик: Листья дерева являются примерами NP-полной проблемы, но их легко решить вручную.

Я: Если примеры легко решить, возможно, проблема не является NP-полной.

Спикер: я не понимаю.

300 долларов, кажется, слишком мало, чтобы зарядить. Это платит только за час или 2 времени. Любое доказательство того, что короткое уже исключено.

Точно нет. Нам не нужна еще одна академическая альтернатива. Некоторые люди уже предоставили эти альтернативы, предоставляя как любителям, так и профессионалам и обществу ложные надежды на будущее в сфере высоких технологий (я имею в виду конкретное место, но я бы не стал его упоминать).

Академическая система была выкована спустя столетия в то, что она есть. Я считаю попытки пропустить систему экспертной оценки просто «пропустить линию». Если исследователь-любитель не в состоянии понять, почему ее доказательство неверно, либо в одиночку, либо с некоторыми комментариями из рецензирования, то существует простое решение, заключающееся в том, что она должна усердно изучать предмет. Вот почему существуют образовательные учреждения, такие как университеты, для сертификации знаний определенного человека. Если этот человек оказывается гением, который мгновенно овладевает знаниями в этой области, хорошо, присудите эту степень как можно скорее. Но подавляющее большинство должно и должно пройти обучение ради себя и общества.

Что бы вы подумали, если бы это направление бизнеса было взято из математики и было занято медициной или другой областью, где последствия были бы более непосредственными? Как долго, пока ненадежный бизнесмен нарочно не изменит любительские бумаги, чтобы их было трудно просмотреть или обмануть рецензента? Обманывают клиентов-исследователей-любителей, как со всеми предприятиями, которые полагаются на трудные знания.

Вы можете видеть, что я хочу сказать, что существуют функциональные проблемы, прежде чем даже углубляться в технические детали. И поскольку я выступаю с инженерным аргументом, «программирование» является хорошим примером того, что происходит, когда любители пытаются выполнять серьезную работу практически без обучения. Последнее, что нужно любому научному сообществу, - это средства массовой информации, прославляющие следующего «ученого-теоретика-самоучку, который бросает вызов основам всего научного сообщества из своего гаража», не говоря уже о хрупкой науке, как наша, которая все еще пытается добиться признания ее заслуживает.