Кез-келген нәтиже NP-толық проблемасын шағын супер-полиномдық уақытпен байланыстырады?

Хело бәріне,

кейбір NP $ толық емес мәселені қосатын кез-келген нәтиже немесе зерттеу бар ма?    сәл супер-полиномиалды (қатты субспоненциалды) уақытпен бірге ме?

Бұл міндетті түрде $ P $ vs $ NP $ проблемасын қарастырмайды (бұл P = NP $, дегенмен).

Рақмет сізге

0
неге жоқ? P ≠ NP QED-ге сәйкес келеді
қосылды автор vzn, көзі
oh жоғарғы дегенді білдіреді ме?
қосылды автор vzn, көзі
@vzn, ол P және NP арасындағы бөлуді қамтамасыз етпесе міндетті емес, мысалы, np-толық мәселені сәл супер-полиномиальді уақытта шешуге болатын нәтиже многодинамикалық алгоритмді жоққа шығармайды
қосылды автор Abhishek Anand, көзі
@vzn, иә ол сондай-ақ жоғарғы шекара болуы мүмкін немесе әлдеқайда супер-полиномиальді уақытта жұмыс істейтін нақты алгоритм, многодинамикалық алгоритмдерді жоққа шығармайды. Егер сізді қызықтыратын болсаңыз, Менің басқа мәселе бойынша
қосылды автор Abhishek Anand, көзі

1 жауаптар

Сізге «сәл супер-полиномиальды» деген неғұрлым нақты болуы керек. Бірақ, бұл жұмыс істей алады: сіз NP-толық мәселені алып, оны жасай аласыз.

Мысалы: кез келген тұрақты $ k \ ge 1 $ үшін, $ n $ -vertex CLIQUE даналары тек шыңдардың $ n ^ {1/k} $ оң дәрежесі болғанда қиын болады (мысалы, $ G = V, E) $ CLIQUE және оған $ | V | ^ {k} - | V | $ оқшауланған шыңдары қосыңыз. Бұл CLIQUE даналары $ 2 ^ {n ^ {1/k}} \ text {poly} (n) $ уақытында шешілуі мүмкін.

7
қосылды
Қарапайым алгоритм барлық оқшауланған шыңдарды алып тастау және содан кейін $ n ^ {1/k} $ қалған шыңдарының барлық ықтимал ішкі жиынын қолдануға тырысады.
қосылды автор Andrew, көзі
+1, ahh nice, бұл өте аз супер-полиномдық деп ойлаймын. Шындығында, жеңіл супер-полиномының шегі дәл көрсетілмеген. Интуитивті ол супер-полиномиальды, бірақ суб-экспоненциалды, нақты шегі - мәселенің өзі. Басқа да жауаптар күтеді
қосылды автор Abhishek Anand, көзі
Осылайша $ k $ шексіздікке ұмтылады, ол многодинамикалық, дұрыс болады?
қосылды автор Abhishek Anand, көзі
Бұл кезде CLIQUE проблемасы үшін $ 2 ^ {n ^ {1/k}} + \ text {poly} (n) $ қалай есептелетінін білгіңіз келсе, немесе кейбір анықтаманы қоссаңыз, өте жақсы болыңыз.
қосылды автор Abhishek Anand, көзі