Кіріспе
Есептеулік проблеманың түрі
Есептеулік күрделілік теориясында уәделік проблема – бұл шешім проблемасының жалпылануы, онда кіріс барлық мүмкін кірістердің белгілі бір кіші жиынына жататыны алдын ала келісілген. Шешім проблемаларынан өзгеше, жауапты жағдайлар (алгоритмнің «иә» деп қайтаруы тиіс кірістер) және жауапсыз жағдайлар кірістердің барлық жиынын толықтырмайды. Анығырақ айтқанда, алгоритмге кіріс жауапты немесе жауапсыз жағдайлар жиынына жататыны алдын ала келісілген. Жауапты да, жауапсыз да емес кірістер болуы мүмкін. Егер мұндай кіріс уәделік проблеманы шешуге арналған алгоритмге берілсе, алгоритм кез келген нәтижені шығаруға құқылы, тіпті тоқтамауы да мүмкін.
In computational complexity theory, a promise problem is a generalization of a decision problem where the input is promised to belong to a particular subset of all possible inputs. Unlike decision problems, the yes instances (the inputs for which an algorithm must return yes) and no instances do not exhaust the set of all inputs. Intuitively, the algorithm has been promised that the input does indeed belong to set of yes instances or no instances. There may be inputs which are neither yes nor no. If such an input is given to an algorithm for solving a promise problem, the algorithm is allowed to output anything, and may even not halt.
Ресми анықтама
Шешімдік мәселе тілмен байланыстырылуы мүмкін, онда мәселе – тілге жататын барлық кірістерді қабылдау және тілге жатпайтын барлық кірістерді қабылдамау. Уәделенген мәселе үшін екі тіл бар, және , олар бір-бірінен бөлек болуы керек, яғни , мұнда тілге жататын барлық кірістер қабылданып, тілге жатпайтын барлық кірістер қабылданылмайды. Бұл жиын уәде деп аталады. Егер кіріс уәдеге жатпаса, шығысқа қатысты талаптар жоқ. Егер уәде бос жиынға тең болса, онда бұл да шешімдік мәселе болып табылады, ал уәде тривиалды деп аталады.
Мысалдар
Көптеген табиғи проблемалар шын мәнінде уәде проблемалары. Мысалы, келесі мәселені қарастырайық: Бағытталған ациклді граф берілген, графикте ұзындығы 10-ға тең жол бар ма, жоқ па, анықтаңыз. Жауап "иә" болса, бұл 10 ұзындығы бар бағытталған ациклді графтар, ал жауап "жоқ" болса, 10 ұзындығы жоқ бағытталған ациклді графтар. Уәде – бағытталған ациклді графтар жиынтығы. Бұл мысалда уәдені тексеру оңай. Атап айтқанда, берілген графтың циклды екенін тексеру өте оңай. Дегенмен, уәде етілген қасиетті бағалау қиын болуы мүмкін. Мысалы, "Гамильтон граф берілген, графикте 4 өлшемді цикл бар ма, жоқ па, анықтаңыз" деген мәселені қарастырайық. Енді уәдені бағалау NP-ге тең қиындық тудырады, бірақ уәде проблемасын шешу оңай, себебі 4 өлшемді циклдерді тексеру полиномиалдық уақытта жүзеге асырылуы мүмкін.