Vad är naturen bakom klassiska beräkningars komplexitetsbegränsingar?

En del beräkningar kräver beviserligen kvantdatorer för att att få en polynomial tidskomplexitet (såvida inte NP=P).

Använder vi oss av klassiska beräkningar och metoder, dvs hjärnan och/eller klassiska datorer så är det ickepolynomiala tidskomplexiteter som gäller.

Vad i det klassiska till skillnad från kvantdatorer är det som oftast sätter undre begränsningar i tidskomplexiteten? Hemligheten bakom kvantdatorer är dess superpositioner, så i någon mening gör dem "flera saker samtidigt". För många problem sänker det kompexliteten en kategori. Jag kan inte tillräckligt om kvantdatorer för att säga så mycket mer än så, men tråden handlar inte om kvantdatorer.

Min fråga är, oavsett om kvantdatorer hade existerat eller inte: är det det sekventiella i klassiska beräkningar som begränsar tidskomplexiteten till en undre gräns? Är en del kombinatoriska problem exponetiella för att vissa problem beräkningsmässigt måste ha tidigare steg uträttade innan följande steg kan utföras och att det i den motsvarande klassiska fysiken (räkneramar, microchip, räkna på fingrarna, var så kreativ du vill) inte finns några genvägar?

Beräkningsmässigt så måste vi med klassiska datorer dela upp problemlösning i flera förutsägbara steg, en algoritm. Dessa algoritmer även om de kan vara parallella till en begränsad konstant jobbar sekventiellt även om vi uttrycker dem abstrakt.

När vi har abstrakta idéer så måste vi ändå konkretisera dem när vi beräknar dem.

Det finns idag t.ex. inga abstrakta lösningsmetoder för SAT-solving t.ex där man på ett abstrakt plan kan slutleda sig till lösningen (snabby och för stora problem alltså). Kan det bero på fundamentala fysiska begränsning ur ett klassiskt perspektiv, vilket även gäller hjärnkraft, som kräver superposition och kvantdatorer och liknande för att få ner komplexiteten?

Det där stämmer inte, såvitt jag vet. Grovers algoritm är bara polynomiellt snabbare än optimala klassiska algoritmer. Shors algoritm är exponentiellt bättre än kända algoritmer men där vet vi inte vad den klassiska komplexiteten är.

Beträffande dina frågor finner jag dem lite svårtydda. Hur som helst rekommenderar jag Scott Aaronsons skriverier i ämnet.

BQP förmodas täcka delar av PSPACE, delar av NP och hela P.

Jag vill dock inte göra en kvantdatortråd av detta.

Frågan är: vad är det där fundamentala som begränsar den undre tidskomplexiteten för klassiska algoritmer.

Svaret ligger i problemens natur och det som algoritmerna modellerar, dvs typ enkla fysiska processer där man flyttar runt och manipulerar symboler och värden.

Du sade att vissa beräkningar bevisligen kräver kvantdatorer för att få polynomiell tidskomplexitet. Såvitt jag vet är detta inte fallet, men jag vill gärna bli rättad om jag har fel.

Som jag skrev: (såvida inte P=NP). Om P=NP, då går NP-problem att lösa klassiskt (bevisat).
Om P != NP så är det bevisat att du inte kan lösa NP-problem klassiskt i polynomisk tid.

Således, behöver du "beviserligen" en kvantdator.

Det finns inget bevis för P != NP om det är det du efterfrågar. Jag utgår ifrån att P != NP och de håller nog de allra flesta med om.

I praktiken spelar det ingen roll då vi inte har ett enda NP-problem som går att lösa på P-tid, då fungerar fortfarande en kvantdator.

Jag utgår från status quo då den inte lär ändras, vilket också är trådens grundförutsättning: att det föreligger fundamentala hinder för det.

När jag tänker efter så vore att kunna svara på tråden fullt ut att kunna bevisa att P != NP. Högoddsare. Men alltid finns det någon kreativ jycke som fyller på med insikt.

Jag är fullt medveten om att P vs. NP är ett öppet problem, men när du skriver att vissa beräkningar "beviserligen" (din stavning) kräver kvantdatorer för att bli polynomiella så är den naturliga tolkningen att det är bevisat att kvantdatorer faktiskt skulle vara exponentiellt snabbare än klassiska datorer för minst ett problem. Och det är det såvitt jag vet inte; det är förmodat men inte bevisat, eftersom vi till exempel inte vet vad den klassiska komplexiteten för faktorisering är. Och eftersom det är en vanlig vanföreställning att det skulle vara bevisat är det mödan värt att påtala detta.

Med det sagt är din frågeställning fortfarande oklar.

Fattar inte vad det finns att gnälla över. Jag har redan sagt mitt gällande allt detta. Du får läsa om trådstarten och fundera på vad som menas, trådstarten är varken tvetydig eller svår att förstå. Du låter som en nybörjare eller någon med tre olika bokstavsdiagnoser.

Förstår inte heller varför du gnäller om faktorisering, var det kom ifrån eller har med tråden att göra. Ännu mer mystiskt är varför du vidare tar upp faktoriseringens komplexitet och gnäller om att den är okänd, förstår inte vad det har med någonting här att göra och vad du försöker argumentera för med det. Den enda slutsats jag kan dra är att du inte vet vad du pratar om och verkar tro att P vs NP uteslutande har med primtalsfaktorisering att göra eller något annat förvirrat.

Jaha, om trådstarten är entydig och lätt att förstå så kan du ju se fram emot en givande diskussion med mindre gnälliga typer än jag. Mycket nöje!

Jag nämner faktorisering uttryckligen som ett exempel på ett problem där kvantdatorer förmodas ge exponentiella vinster. Men det är som sagt inte bevisat. Och det är såvitt jag vet inte bevisat i något annat fall heller, och därmed är din inledning missvisande, vilket var min poäng hela tiden.

Det är förmodat att NP-problem klassiskt sett är begränsade till den klassiska komplexitet vi idag förmodar att de har (och det har ingenting med faktorisering att göra). Ja, detta är förmodat och det är utifrån den förmodan (att om förmodan stämmer:) formellt bevisat (således beviserligen) att det krävs kvantdatorer eller annan icke-klassisk lösning. Det jag tydligt uttryckt flera gånger är att det ändock är irrelevant för tråden huruvida kvantdatorer kan nå sina mål och varför detta inte är en kvantdatortråd. När du är ute på de spåren så är du ute på helt fel spår och i fel riktning.

Utgångspunkten här är givetvis att N != NP och det är en fullständigt sund utgångspunkt. Man kan också komma fram till motsatsen då diskussionen frågar "varför dessa klassiska övre tidskomplexitetsbränsningar finns" och påstå att så inte är fallet. Det finns inga som helst tvetydigheter i detta då P vs NP inte är löst och alla diskussioner därmed är teoretiska. Någon som forskar i fältet och i vanlig "folkmun" säger man rakt ut att "detta problem är NP-hard och har en exponentiell tidskomplexitet", men man avslutar aldrig en sådan mening med "förmodar vi", särskilt inte alltid. Därav antar jag att du är mycket ovan med att föra sådana här diskussioner. Man antar att P != NP i praktiken tills det är bevisat eller motbevisat och att det är ett öppet problem är underförstått.

Det du gör är lite som att som kanske något introduktions-kunnig men mycket ovan glida in i en gravitationsdiskussion och seriöst säga att "det är inte bevisat att vi inte kan blockera gravitoner och således sväva" när någon påstår att äpplet måste falla ner och att "kvantfluktationer kan accelera äpplet uppåt".

Vet du vad jag egentligen tror att det här handlar om? Jag tror att du är rasist och homofob som religiöst följer nazismen.