Czy istnieje sposób, w jaki przysłowie może przekonać weryfikatora, że niektóre wyrażenia HORN-SAT są zadowalające?
Oczywiście może się to wydawać głupie, ponieważ istnieją algorytmy czasu liniowego dla HORN-SAT. Z drugiej strony HORN-SAT jest P-zupełny, co oznacza, że nie ma algorytmów przestrzeni logów, chyba że P = L. W związku z tym ogranicz możliwości obliczeniowe weryfikatora do L. Teraz weryfikator jest bardzo słaby, więc problem nie jest już głupi.
Kolejnym zwrotem jest to, czy może to być dowód braku wiedzy.
1
W przypadku niezerowej wiedzy uważam, że naiwna weryfikacja przy użyciu zadowalającego przypisania prawdy jako certyfikatu wymaga tylko miejsca w dzienniku, pod warunkiem, że dane wejściowe i certyfikat są zapisane na taśmach tylko do odczytu, które nie liczą się jako spacja.
—
Tsuyoshi Ito,
@Tsuyoshi: Nie widzę, jak dokonywać naiwnej weryfikacji tylko w przestrzeni dziennika. Jeśli moglibyśmy, czyż nie pokazałoby to, że HORN-SAT jest w NL, a zatem przez P-kompletność daje P = NL?
—
Shaun Harker
Nie. Zakładam, że certyfikat znajduje się na taśmie tylko do odczytu, co różni się od weryfikacji przeprowadzanej przez NL.
—
Tsuyoshi Ito
@Tsuyoshi: Ach, więc możesz czytać certyfikat wiele razy, podczas gdy oparta na certyfikatach definicja NL miałaby certyfikat, który można odczytać tylko raz.
—
Shaun Harker,