(Wie) Können wir NP-Probleme in Abwesenheit des Turing-Berechnungsmodells entdecken / analysieren?

Wie kann man aus rein abstrakten mathematischen / rechnerischen Gesichtspunkten überhaupt Probleme wie 3 - SAT, Teilmenge Summe, Handlungsreisender usw. Entdecken oder über sie nachdenken? Wären wir überhaupt in der Lage, sie nur unter funktionalen Gesichtspunkten sinnvoll zu beurteilen? Wäre es überhaupt möglich?

Ich habe diese Frage nur von einem Punkt der Selbstuntersuchung aus betrachtet, als Teil des Lernens des Lambda-Kalkülmodells der Berechnung. Ich verstehe, dass es "nicht intuitiv" ist und deshalb hat Godel das Turing-Modell bevorzugt. Ich möchte jedoch nur wissen, wo die bekannten theoretischen Einschränkungen dieses funktionalen Rechenstils liegen und wie hinderlich es wäre, die NP-Klasse von Problemen zu analysieren.

Möglicherweise möchten Sie sich die Kostensemantik für funktionale Sprachen ansehen . Dies sind verschiedene Rechenkomplexität Maßnahmen für funktionale Sprachen , die sie nicht durch jede Art von Turing - Maschine passieren, RAM - Maschine, usw. Ein guter Ort zu beginnen, ist diese Lambda the Ultimate Post , die einige gute mwN hat.

In Abschnitt 7.4 von Bob Harpers praktischen Grundlagen für Programmiersprachen wird die Kostensemantik erläutert.

Die Arbeit über die relative Nützlichkeit von Feuerbällen von Accattoli und Coen zeigt, dass Kalkül in Bezug auf das RAM-Maschinenmodell höchstens eine lineare Aufblähung aufweist.$\lambda$

Zusammenfassend wäre es auf diesem anderen Planeten in Bezug auf NP ziemlich ähnlich, aber es würde weniger Pufferüberläufe geben und es würde nicht so viel Müll herumliegen.

Auf Bitte von Andrej und PhD verwandle ich meinen Kommentar in eine Antwort mit Entschuldigung für die Eigenwerbung.

$\mathsf{NP}$

• $$\frac{\text{Boolean circuits}}{\text{Turing machines}}=\frac{\text{affine $\lambda$-terms}}{\text{$\lambda$-terms}}$$ $\lambda$
• $\lambda$
• $\mathsf{NP}$
• Natürlich kann man dann HO CIRCUIT SAT auf CIRCUIT SAT reduzieren, was das übliche Cook-Levin-Theorem beweist, und die blutigen Details auf niedriger Ebene werden alle verschoben, um eine solche Reduzierung zu erstellen.

$\mathsf{NP}$

$\lambda$$\lambda$

$\mathsf{NP}$

$\lambda$

$\lambda$

$\mathsf{NP}$$\mathsf{NP}$$\mathsf{coNP}$$\lambda$

$\lambda$$\lambda$

$\mathsf{NP}$$\lambda$Es spielt keine Rolle, ob Sie wissen, dass Ihre Intuitionen gesund sind. Turing-Maschinen gaben eine sofortige und praktikable Antwort, und die Menschen hatten (und haben immer noch nicht) das Bedürfnis, noch weiter zu gehen.