Бұл нөлдік бағдарламалау APX-де жоқ екенін қалай көрсетуге болады?

Бұл нөлдік бағдарламалау APX-де жоқ екенін қалай көрсетуге болады?

  • Vertex Cover проблемасы APX класында. Сонымен, PTAS-ны төмендетуді қолдана аламын ба? нөлдік бір бағдарламалау мәселесі Vertex қақпағына және оның азаюын көрсетіңіз осы мәселелердің арасында?

  • Қайдан бастау керек

  • Біреу осындай тақырыптағы қағазды біле ме?

Мен кез келген кеңес үшін алғысымды білдіремін.

0
Неге сіз мұны көрсетгіңіз келеді?
қосылды автор alumb, көзі
Яғни, қағазға немесе презентацияға керек пе?
қосылды автор alumb, көзі
APX NPO-ның тиісті жиынтығы екенін көрсету.
қосылды автор Steve Linton, көзі
Маған оқу мақсатына қажет. Бірақ, ең алдымен, тақырыпты қалай бастау керектігі туралы түсінік қажет.
қосылды автор Steve Linton, көзі
Бұл проблемаға Log-APX қатты, Poly-APX қатаң, Exp-APX қатты немесе NPO қателігін азайтыңыз және ол APX ішінде P! = NP болғанда болмайтындығын дәлелдей аласыз.
қосылды автор geewhiz, көзі

Жауап жоқ

0