Бізде нетривиалды бірыңғай тізбектер бар ма?

$ T (n) $ уақытында жұмыс істейтін алгоритмді ескере отырып, оны $ \ approx t (n) \ log t (n) $ шамасында бірдей мәселе үшін «тривиалдық» біркелкі торлы отбасына айналдыра аламыз.

Екінші жағынан, егер $ t (n) $ оңтайлы жұмыс уақыты болса да, бізде осы мәселе бойынша біршама кішкентай бірыңғай тізбектер бар болуы мүмкін. Схемалар генерациялау үшін $ t (n) $ артық болуы мүмкін, бірақ олар кішкентай.

Бірақ мұндай заттарды қалай жасау керектігін білеміз бе? Менің ойымша, сұрақ қоюдың бастапқы сұрағы бар

(1) Бізде бірдей проблемаға арналған кез-келген алгоритмнің ең танымал жұмыс уақытынан аз өлшемі бар біркелкі емес тізбектердің, мысалы, i.e. конструктивті мысалдары бар ма?

Егер $ \ mathsf {DTIME (t (n))} $ проблемасы болса, онда бізде оңтайлы тізбектерді табу үшін экспоненталық уақыт алгоритмі бар деп есептеймін: $ n $ ескере отырып, барлық $ 2 ^ n $ кірісіне жауаптар (уақытты $ (2 ^ n) t (n) $); онда барлық дұрыс жауаптарды беретін біреу табылғанша барлық тізбектерді $ n $ кірісіне көбейтеді. Іздеу тривиалдық түрлендірудің өлшемдерінде, $ t (n) \ log t (n) $ немесе функцияның шындық кестесімен аяқталады, егер $ \ {0,1 \} $ болса, $ 2 ^ n $. (Өңдеу: Тома Шэннон/Лупановтың арқасында шекара $ O (2 ^ n/n) $ екендігін көрсетеді.)

Сонымен, бізде сұраққа қанағаттанарлықсыз «иә» бар (1): $ 2 ^ n $ жоғары кез келген уақытта қиын, бірақ әлі де жарамсыз тілге ие болыңыз; жоғарыда келтірілген әдіс $ 2 ^ n $ өлшемінің шындық кестесін шығарады.

Сондықтан біз сұрақты нақтылауымыз керек (1). Менің ойымша, ең қызықты екі жағдай

(2) Бізде полиномиальды өлшемді нетривиальды бірыңғай тізбектердің конструктивті мысалдары бар ма? (Тым баяу алгоритмдер арқылы жасалған болса да)

     

(3) Бізде полиномиальді уақыт генерациялайтын , полиномиальды өлшемді нетривиальды емес бірыңғай тізбектердің конструктивті мысалдары бар ма?

Бұл сұрауға тым көп болуы мүмкін. Оңай мәселе туралы: Бізде осындай нәрсе бар екенін білеміз бе? Мүмкін, нетривиалдық емес бірыңғай тізбектер бар ма?

(4) $ s (n) = o (2 ^ n) $ кез келгені үшін келесі мәлімдеме дұрыс емес пе? Егер $ L $ $ $ O (s (n)) өлшем бірліктерінің бірдей тізбегі бар болса, онда ол сондай-ақ уақытша жұмыс істейтін алгоритмдер бар $ \ тильда {O} (s (n)) $. « (Егер солай болса, онда «біркелкі» дегенді «полиномиальды-уақыт бірлігі», «logspace uniform» және т.б. ауыстырған кезде?)

Соңында, егер жоғарыда аталған сұрақтар тым қиын болса,

(5) Бізде тек схемалардағы алгоритмдерді (немесе шындық кестесін жазуды) жай ғана емес айнымалылардың бірыңғай отбасыларының конструкциялары бар ма?

PostScript. Мен сарапшыдан «Орташа-біркелкі және орташа төменгі шекараларда» (« pdf ), Santhanam және Williams 2013, мүмкін ең тығыз байланысты жұмыс, бірақ ол төменгі шектерді дәлелдейді (бұл полиэтикалық генерациялайтын схемалар де күшті емес). Мен кез-келген басқа жұмысқа қызығушылық танытады!

13
1,2,3,4: Жеке басын анықтау функциясы. 5. «Алгоритмдерді тізбектерге айналдыру» деген сөздің мағынасы түсініксіз, біз әрқашан бірыңғай тізбекті Тьюринг машинасына айналдыра аламыз (шағын үстеме).
қосылды автор Swinders, көзі
@Joshua, біз O (n) өлшемінің бірыңғай тізбегін тікелей сипаттай аламыз, ол Turing машинасын схемаға сәйкестендіруге қарағанда жақсы.
қосылды автор Swinders, көзі
Менің ойымша, мәселені жауапты ету үшін қамқорлық жасау керек маңызды шағын бөлшектер бар. Тағы бір мысал: BPP P/poly және айырбастау есептеледі. Егер схема генерациясы тиімді алгоритм арқылы жүзеге асырылса, оны сұлбалық мәнмен біріктіретін тиімді ТМ береді. Тұжырымдама схемасы мен ТМ бірдей алгоритмді есептейді. Мөлшер мен уақыттың дәл сәйкес келмеуі қалыпты болып табылады, олар әртүрлі есептеу модельдері үшін анықталған және олар сәйкес келмейтінін білеміз. Мүмкін, уақыт өлшемі қарағанда тереңірек.
қосылды автор Swinders, көзі
тым көп сұрақтар, олардың бөлінуін ұсынамыз ... келісілген . біртектес схемалар мен ТМ төменгі шекаралары негізінен нақты немесе дерлік тұрақты факторлар (яғни, үлкен-Oh шекаралары) ішінде бір-бірімен алмастырылады, дұрыс? сондықтан uniform схемалары туралы мәселе бірнеше артық емес сияқты, бірақ кез-келген төменгі шектер туралы сұрауға болады (afaik ешқандай шектеусіз/біркелкі төменгі шекара біркелкі шекарасынан төмен дәлелденген, дұрыс?). сұрақтар да дәлелдемелер/алгоритмдер арасында байланысын жоғалтқан сияқты көрінеді, себебі Curry-Howard корреспонденциясында алгоритмдерге айналуға болмайтын дәлелдер жоқ.
қосылды автор vzn, көзі
??? р (2)/(3) - бұл төменгі немесе жоғарғы шекара? all алгоритмдері P жеткілікті ме? Томас жауапында айтылған уақыттық иерархиялық теореманың құрылысы (негізінен санақтарды санау/әмбебап ТМ-ді «сағаттармен» имитациялау) тіпті мұндай тілдерді генерациялау/аудару мүмкін ... juknas тамаша реф логикалық қателердің күрделілігі жалпы аумақтағы сауалнама үшін ...
қосылды автор vzn, көзі
@Kaveh: сәйкестендіру функциясы 1-4 қалай жауап береді?
қосылды автор William S. Godfrey- S.E., көзі
@Kaveh, 5-ші сұрақ: Жақсы нүкте, бірақ менің ойымша, біреу біреудің «бірыңғай тізбекті айналдыруға» ұқсас емес бірыңғай тізбектердің құрылысын жазады деп ойлаймын. Сондай-ақ, айтатын болсаңыз, контур «алгоритмге ұқсайды» дегенді білдірмейді. Мәселен, бізде $ n $ 3 $ уақытты алу үшін $ n $ схемасы бар дейді. Біз оны $ n ^ 3 $ TM уақытына айналдыра аламыз, бірақ ол схемаға өте ұқсас емес, және сол ТМ-ны қайтадан айналдыруға айналдыру енді ~ $ n ^ 3 $ өлшемі. Бұл мәселе мені қызықтыратындығын көрсетеді.
қосылды автор drsnyder, көзі
@Kaveh, жоғарыда айтқанымдай, сол мәселе бойынша TM сияқты «i> ештеңе көрінбейтін« шағын »тізбектер болуы мүмкін. (Немесе ... мүмкін емес пе?) Бұл полиомиелді уақытта осы тізбектерді жасай алатыны олардың құрылымы «тривиальды» түрлендірілген-ТМ тізбектерінен түбегейлі айырмашылығы болады дегенді білдірмейді. Уақыттың өлшемі мұнда маңызды емес; онда олар «тривиальность» және «нетривиальность» туралы жазуға мүмкіндік береді.
қосылды автор drsnyder, көзі
@vzn, (2)/(3) жоғарғы шекараны сұрайды, яғни, (5) ең жақсы белгілі тривиал-айырбастау-TM-ге қарағанда асимптоталық жақсы жауаптар.
қосылды автор drsnyder, көзі

1 жауаптар

Міне, соңғы екі сұраққа жауап.

(5) Сұрыптау желілері - ең жақсы RAM алгоритмі сияқты жылдам сұрыпталатын бірыңғай тізбектер, бірақ олар тек RAM алгоритмдерін (мысалы, қышқыл) өзгертпейді. AKS83 , G14 ]

(4) Yes, for any $s(n)=(1+\varepsilon) \cdot 2^n/n$ with $\varepsilon>0$, but for a silly reason: Every function is computed by a circuit of size $(1+o(1)) \cdot 2^n/n$. (Shannon proved this up to a constant and Lupanov got the optimal constant.) By the time hierarchy theorem, there exists a function $f$ with uniform time complexity between $\Omega(3^n)$ and $O(n \cdot 3^n)$. This gives a counterexample: $f$ has circuits of size $O(2^n/n)$ (which I think are computable in $2^{\mathrm{poly}(n)}$ time) but is not computable in $\tilde{O}(2^n/n)$ time. You should probably ask for $s(n) = o(2^n/n)$.

Бұл қызықты мәселе; Деп үміттенемін біреу жауап бере алады (1) - (3).

8
қосылды
Рахмет, сіз дұрыссыз, мен интуитивті осы «жоғарғы шекара» ісін жоққа шығарғым келді, бірақ дұрыс асимптотты білмеді. Мен бұл мәселені қосу үшін сұрақты өзгерттім.
қосылды автор drsnyder, көзі