Алгоритмнің конструктивті емес болуының дәлелі - Википедия - Non-constructive algorithm existence proofs

Туралы оң нәтижелердің басым көпшілігі есептеулер болып табылады сындарлы дәлелдер яғни, есептеулерді шешуге болатындығын дәлелдеу арқылы дәлелдеуге болады алгоритм оны шешеді; есептеу есептері көрсетілген P (күрделілік) оны уақытында шешетін алгоритмді енгізу өлшемі бойынша көпмүшелік көрсету арқылы; т.б.

Алайда, олардың бірнешеуі бар конструктивті емес нәтижелер, мұнда алгоритмнің өзі көрсетілмей алгоритмнің бар екендігі дәлелденеді. Осындай тіршілік ету дәлелдерін ұсыну үшін бірнеше әдістер қолданылады.

Белгісіз ақырлы жиынды қолдану

Комбинаторлық ойындар теориясында

Конструктивті емес алгоритмнің қарапайым мысалы 1982 жылы жарияланған Берлинамп, Джон Х.Конвей, және Ричард К. Гай, олардың кітабында Математикалық пьесалар үшін жеңіске жету жолдары. Бұл ойынға қатысты Сильвер монеталары, онда ойыншылар кезек-кезек позитивті санды көрсетеді, оны бұрын көрсетілген мәндердің қосындысы түрінде көрсетуге болмайды, ал ойыншы 1 санын көрсетуге мәжбүр болған кезде ұтылады, алгоритм бар (кітапта схема ретінде берілген) берілген бірінші жүрістің жеңіп немесе ұтылғанын анықтау үшін: егер ол а жай сан үштен үлкен, немесе шекті жиынының бірі 3 тегіс сандар, содан кейін бұл ұтылған бірінші қадам, ал әйтпесе ол ұтылады. Алайда, ақырғы жиынтығы белгісіз.

Графикалық теорияда

Мәселелеріне конструктивті емес алгоритмдік дәлелдеулер графтар теориясы 1988 жылдан бастап зерттелді Майкл Феллоус және Майкл Лэнгстон.[1]

Графтар теориясында жиі кездесетін мәселе - белгілі бір кіріс графигінің белгілі бір қасиеті бар ма. Мысалға:

Кіріс: график G.
Сұрақ: мүмкін G екі өлшемді емес цикл болмайтындай етіп 3 өлшемді кеңістікке ендірілген G топологиялық байланысты (тізбектің буындарындағыдай)?

3d кеңістігіне енгізілген екі циклдің байланысы бар-жоғын шешетін жоғары экспоненциалды алгоритм бар және графиктегі барлық цикл жұптарын тексеруге болады, бірақ 3d кеңістіктегі барлық ендірулерді қалай есепке алу керек екендігі анық емес. Сонымен, байланыс проблемасы шешімді болса, бұл ап-априорлық емес.

Алайда, көпмүшелік уақытта байланыстырушылықтың шешілетіндігін көрсететін конструктивті емес дәлел бар. Дәлел келесі фактілерге сүйенеді:

  • Жауап «иә» болатын графиктердің жиынтығы қабылданбайды кәмелетке толмағандар. I., Егер G графигін 3-d кеңістікке сілтемесіз енгізуге болатын болса, онда G-дің кез-келген миноры сілтемесіз енгізілуі мүмкін.
  • Әр екі график үшін G және H, көпмүшелік уақыт аралығында ма екенін табуға болады H кәмелетке толмаған G.
  • Авторы Робертсон - Сеймур теоремасы, кез-келген ақырлы графиктердің жиынтығында минимал-минималды элементтердің тек ақырғы саны болады. Атап айтқанда, «иә» даналарының жиынтығында минималды-минималды элементтердің ақырғы саны бар.

Кіріс сызбасы берілген G, келесі «алгоритм» жоғарыдағы мәселені шешеді:

Әрбір минималды элемент үшін H:
Егер H кәмелетке толмаған G содан кейін «иә» деп қайтарыңыз.
«жоқ» деп қайтару.

Мұндағы конструктивті емес бөлік - Робертсон - Сеймур теоремасы. Минор-минималды элементтердің ақырғы саны бар екеніне кепілдік бергенімен, бұл элементтердің не екенін айтпайды. Сондықтан біз жоғарыда аталған «алгоритмді» шынымен орындай алмаймыз. Бірақ, біз алгоритмнің бар екенін және оның орындалу уақыты көпмүшелік екенін білеміз.

Шешімділігін дәл осылай дәлелдеуге болатын көптеген ұқсас проблемалар бар. Кейбір жағдайларда, мәселені көпмүшелік уақытта дәлелдеуге болатындығы туралы білім зерттеушілерді мәселені мүлдем басқаша шешетін нақты полиномдық уақыт алгоритмін іздеуге және табуға мәжбүр етті. Бұл сындарлы емес дәлелдердің сындарлы нәтижелерге әкелетіндігін көрсетеді.[1]

Негізгі идея - есепті параметр ретінде, белгісіз жиынтығын қолданатын алгоритмді қолдану арқылы шешуге болады. Жиын белгісіз болғанымен, біз оның ақырлы болуы керек екенін білеміз, демек, көпмүшелік уақыт алгоритмі бар.

Ұқсас техникамен шешуге болатын көптеген басқа комбинаторлық мәселелер бар.[2]

Алгоритмдерді санау

Кейде берілген есептің потенциалды алгоритмдерінің саны ақырлы болады. Біз мүмкін алгоритмдердің санын санап, олардың тек шектелген саны «жаман» екенін дәлелдей аламыз, сондықтан кем дегенде бір алгоритм «жақсы» болуы керек.

Мысал ретінде келесі мәселені қарастырыңыз.[3]

Мен векторды таңдаймын v тұрады n 0 мен белгілі бір тұрақты арасындағы бүтін сандар болатын элементтер г..

Сіз болжауыңыз керек v сұрау арқылы сұраныстар, бұл форманың сұраныстары: «индекстері бар элементтердің қосындысы дегеніміз не? мен және jЖиынтық сұрау 1-ден бастап кез-келген индекстер санына қатысты болуы мүмкін n.

Сізге қанша сұрақ керек? Әрине, n сұраулар әрқашан жеткілікті, өйткені сіз пайдалана аласыз n бір элементтің «қосындысын» сұрайтын сұрақтар. Бірақ қашан г. жеткілікті аз, одан да жақсысын жасауға болады. Жалпы идея келесідей.

Әр сұранысты 1-ден- түрінде ұсынуға боладыn элементтері барлығы {0,1} жиынында болатын вектор. Сұрауға жауап дегеніміз - сұрау векторының нүктелік көбейтіндісі ғана v. Әрбір жиынтығы к сұраныстармен ұсынылуы мүмкін к-n матрица {0,1} жоғары; жауаптар жиынтығы - матрицасының көбейтіндісі v.

Матрица М «жақсы», егер ол бізге бірегей анықтауға мүмкіндік берсе v. Бұл дегеніміз, әр вектор үшін v, өнім M v бірегей. Матрица М егер екі түрлі вектор болса, «жаман», v және сен, осылай M v = M u.

Кейбір алгебраның көмегімен «жаман» матрицалар санын шектеуге болады. Шектелген функциясы г. және к. Осылайша, жеткілікті аз г., кішкентаймен бірге «жақсы» матрица болуы керек к, бұл сәйкестендіру мәселесін шешудің тиімді алгоритміне сәйкес келеді.

Бұл дәлел екі жолмен конструктивті емес: жақсы матрицаны қалай табуға болатындығы белгісіз; және жақсы матрица берілсе де, векторды сұраным жауаптарынан қалай тиімді қайта құру керектігі белгісіз.

Осыған ұқсас көптеген басқа проблемалар бар, оларды дәл осылай шешуге болатындығын дәлелдеуге болады.[3]

Қосымша мысалдар

Әдебиеттер тізімі

  1. ^ а б Стипендиаттар, М.Р .; Langston, M. A. (1988). «Көпмүшелік-уақыттық шешімділікті дәлелдеудің конструктивті емес құралдары». ACM журналы. 35 (3): 727. дои:10.1145/44483.44491. S2CID  16587284.
  2. ^ Браун, Дж .; Стипендиаттар, М.Р .; Langston, M. A. (2007). «Полиномдық уақыттың өзін-өзі төмендетуі: теориялық мотивтер және практикалық нәтижелер». Халықаралық компьютерлік математика журналы. 31 (1–2): 1–9. дои:10.1080/00207168908803783.
  3. ^ а б Гребинский, V .; Кучеров, Г. (2000). «Қосымша модель бойынша графиктерді оңтайлы қайта құру» (PDF). Алгоритмика. 28: 104–124. дои:10.1007 / s004530010033. S2CID  33176053.
  4. ^ Киммел, С. (2013). «Кванттық қарсылас (жоғарғы) шекара». Чикаго журналы Теориялық информатика журналы. 19: 1–14. arXiv:1101.0797. дои:10.4086 / cjtcs.2013.004. S2CID  119264518.

Несиелер

Осы парақтағы сілтемелер төмендегілерден жинақталды Stack Exchange жіптер:

Сондай-ақ қараңыз