Klausimai pažymėti „p-np“

Naudojamas klausimams apie problemą P vs NP.
6
atsakymai

Kas yra "P = NP?", Ir kodėl toks toks garsus klausimas?

Klausimas, ar P = NP yra bene labiausiai žinomas visuose kompiuterių moksluose. Ką tai reiškia? Ir kodėl taip įdomu? Oi, ir už papildomą kreditą, prašome pateikti įrodymų apie tiesą ar netikrumą. :)
nustatyti 21 rugsėjo '08, 7:07 val
7
atsakymai

Paaiškinkite Vinay Deolilikar įrodymą, kad P! = NP

Neseniai buvo paskelbtas „Vinay Deolilicar“ paskelbtas straipsnis „HP Labs“, kuriame teigiama, kad įrodė, jog P! = NP. Ar kas nors gali paaiškinti, kaip šis įrodymas veikia mažiau matematiškai linkusiems žmonėms?
nustatyti 09 rug. '10, 5:22
6
atsakymai

Ar NP sunkūs klausimai, kurie nėra sunkūs, sunkiau?

Mano nuomone, visos NP užbaigtos problemos yra sunkios NP, bet kai kurios NP sunkios problemos nėra žinomos kaip „NP“, o „NP“ sunkios problemos yra bent jau tokios pat sudėtingos, kaip ir visos NP problemos. Ar šios sudėtingos NP sunkios problemos ...
Nustatykite rugsėjo 28 d '10, 8:26
15
atsakymai

Kokia yra hipotetinė hipotezė P = NP?

Ar tai bus specifinis NP-užbaigtos problemos polinomo laiko algoritmas, ar yra tik abstrakčių argumentų, rodančių NP-užbaigtų problemų sprendimus? Atrodo, kad konkretus algoizmas yra daug naudingesnis. Šiuo atveju, viskas, ko mums reikia ...
gegužės 23 d
5
atsakymai

Kodėl vadinamos NP problemos (tiek „NP“, tiek „NP“)?

Iš tiesų. Paskutinį egzaminą turiu paskutinį egzaminą šį antradienį, ir tai yra vienas iš dalykų, kuriuos aš niekada nesupratau. Suprantu, kad NP problemos sprendimas gali būti patikrintas polinominiu laiku. Bet ką turi daryti su determinizmu?
nustatyti 08 rugsėjis '10 23:00 val
8
atsakymai

Trūksta šio įrodymo P! = NP?

Bandžiau iš naujo nustatyti slaptažodį. Kai galvojau apie tai, supratau, kad „slaptažodžio atkūrimo“ problema yra labai geras NP problemos pavyzdys. Jei žinote slaptažodį, jį labai lengva patikrinti polinominiu laiku. BET, jei nežinote slaptažodžio, jums reikia ...
12 d '09 11:56
4
atsakymai

„Viso kodo paieška tam tikrame dvejetainiame faile yra lygi„ užbaigimo “problemai.

Tiesiog perskaitykite labai balsuotą klausimą apie emuliatorius ir pareiškimą Buvo įrodyta, kad rasti visą kodą šiame dvejetainiame ekvivalente yra lygus sustojimo problemai. Tiesą sakant, aš suklupau ant manęs. Ar tai tikrai negali būti tiesa? Sukurti ...
yra nustatytas kovo 14 d. 11 val
1
atsakymas

P = NP: Kokie yra perspektyviausi metodai?

Žinau, kad P = NP vis dar nėra išspręsta, bet ar kas nors gali man pasakyti, kas yra šiuo metu perspektyviausi matematiniai / kompiuterių mokslo metodai, kurie gali būti naudingi sprendžiant šią problemą? Arba taip ...
Nustatyta gegužės 25 d. 10 val
3
atsakymai

Ar išspręstos P-NP problemos? Ar FindBugs išsprendžia sustabdymo problemą?

Yra įrankis, vadinamas „FindBugs“, galintis aptikti begalines begalines kilpas tam tikroje programoje / kodo bazėje. Tai reiškia, kad „FindBugs“ gali nustatyti, ar programa baigsis, ar ne, analizuodama kodą. Su likusia problema ...
lapkričio 19 d. '13, 11:50
2
atsakymai

Kokia yra problema su NP?

Aš perskaičiau straipsnį apie Vikipediją, bet negalėjau suprasti, kas tiksliai yra NP. Ar kas nors apie juos gali pasakyti ir apie tai, kas su jais susijusi su P problemomis?
rugpjūčio 17 d. '10, 13:01
2
atsakymai

Ar gali būti rūšiavimas P, NP ir NP-Complete?

Esu labai supainiotas, ir tai yra mano mintis po tam tikro skaitymo: P yra NP, o NP - „NP-Complete“. Todėl visi „P“ gali būti „NP“ ir „NP-Complete“? Ar tai reiškia, kad yra rūšiavimo algoritmai, kurie gali būti NP ir „NP-Complete“? Nadeyus ...
12 d '12 13:18
2
atsakymai

Ar eksponentinė apatinė riba NP pilnoje kalboje įrodo, kad P nėra lygus NP?

Jei kas nors galėtų įrodyti, kad NP-pilnai problemai yra eksponentinė apatinė riba, ar tai įrodytų, kad P ≠ NP?
lapkričio 18 d. '13, 11:22
1
atsakymas

Primes P - kaip dirbti iki sqrt?

Aš tiriu P ir NP. Aš perskaičiau, kad problema sprendžiant, ar tam tikras skaičius yra paprastas, yra problema P, o tai reiškia, kad ji turi polinomo laiko algoritmą, kuris jį išsprendžia. Taip pat perskaičiau, kad šis faktas buvo įrodytas 2002 m.
Nustatykite rugpjūčio 16 d '14, 19:21
1
atsakymas

3SAT sprendimas, nors DNF supaprastinimas?

Aš galvojau apie 3SAT problemos sprendimo algoritmą, naudodamas žemiau pateiktą metodą: 1) Paimkite visus cnf lygties sakinius, turinčius bent vieną kintamąjį. Raskite visus tokius derinius ir įtraukite juos į sąrašą, pavadintą „sankryža“. Sąrašas "...
rugsėjo 13 d 15 val
1
atsakymas

Sumažinti nuo A iki B: tiesa arba klaidinga

Yra du teiginiai: jei tirpalo A problema yra polinominis laikas, sumažinamas iki B problemos sprendimo (m. A≤ pB), o B yra NP-pilnas, tada A turi būti NP-pilnas. Taip pat: Jei B sprendimo problema yra polinomas laikas, tada ...
nustatyti 04 gruodis '15, 4:52