Кіріспе
Кіші схемалармен шешілетін проблемалар жиынтығы
Есептеу күрделілігі теориясында P/poly – шағын схемалармен шешілетін проблемаларды білдіретін күрделік класы. Нақтырақ айтқанда, бұл полиномдық өлшемдегі схемалар отбасы бар формальды тілдер жиынтығы. Оны Тьюринг машинасына кірісімен бірге берілетін қосымша кеңес ретінде де анықтауға болады, бұл кеңес кіріс ұзындығына байланысты болуы мүмкін, бірақ кірістің өзіне емес. Осы тұжырымдама бойынша P/poly – кіріс өлшемінде полиномдық ұзындығы бар кеңес тізбектерімен жұмыс істейтін полиномдық уақыт Тьюринг машинасымен шешілетін шешімдер класы. Бұл екі түрлі анықтама P/poly-ді схема күрделігі және біртекті емес күрделік үшін маңызды етеді. Мысалы, танымал Миллер-Рабин біріншілік тестісін P/poly алгоритмі ретінде құруға болады: «кеңес» – сынауға болатын мәндердің тізімі. Кез келген құрама сан үшін, тізімде куәгер болатын мәндердің тізімін алдын ала есептеуге болады. Мысалы, 32 биттік сандардың біріншілігін дұрыс анықтау үшін, тек сынау жеткілікті. Үміткер куәгерлердің қысқа тізімдерінің болуы, әр құрама сан үшін төрт үміткердің үшінің оны құрама екенін анықтай алатынынан туындайды. Осыдан, BPP P/poly дәлеліндегіге ұқсас қарапайым санау аргументі, әрбір кіріс өлшемі үшін қолайлы үміткер мәндер тізімі бар екенін көрсетеді, және одан да күштірек, жеткілікті ұзын үміткер мәндер тізімдері дұрыс жұмыс істейтінін, бірақ жұмыс істеуіне кепілдік берілген тізімді табу қымбатқа түсуі мүмкін екенін көрсетеді.
In computational complexity theory, P/poly is a complexity class representing problems that can be solved by small circuits. More precisely, it is the set of formal languages that have polynomial size circuit families. It can also be defined equivalently in terms of Turing machines with advice, extra information supplied to the Turing machine along with its input, that may depend on the input length but not on the input itself. In this formulation, P/poly is the class of decision problems that can be solved by a polynomial time Turing machine with advice strings of length polynomial in the input size. These two different definitions make P/poly central to circuit complexity and non uniform complexity. For example, the popular Miller–Rabin primality test can be formulated as a P/poly algorithm: the "advice" is a list of candidate values to test. It is possible to precompute a list of values such that every composite bit number will be certain to have a witness in the list. For example, to correctly determine the primality of 32 bit numbers, it is enough to test The existence of short lists of candidate witnesses follows from the fact that for each composite , three out of four candidate values successfully detect that is composite. From this, a simple counting argument similar to the one in the proof that BPP P/poly below shows that there exists a suitable list of candidate values for every input size, and more strongly that most long enough lists of candidate values will work correctly, although finding a list that is guaranteed to work may be expensive.
P/poly-де шектелген қателікпен ықтималдық полиномиалы бар
Адлеман теоремасы BPP ⊆ P/poly екенін айтады, мұндағы BPP – полиномиал уақыт ішінде екі жақты қателікпен жұмыс істейтін кездейсоқ алгоритмдермен шешілетін мәселелер жиыны. Бастапқыда Леонард Адлеман нашаррақ нәтижені дәлелдеген, атап айтқанда, RP ⊆ P/poly; ал бұл нәтиже Бэннет пен Гиллдің жұмысымен BPP ⊆ P/poly түрінде жалпыланды. Теореманың нұсқалары BPL L/poly-де, ал AM NP/poly-де қамтылғанын көрсетеді.