Logicus-constructief vervangen door combinatoristisch-constructief?

Logici interpreteren het woord "constructief" op een zeer goed gedefinieerde manier: ze bedoelen het, min of meer, "berekenbaarheid". Constructiviteit serieus nemen en werken in een wereld waar alles constructief moet zijn, leidt tot intuïtionistische logica, wat een zeer productief en fascinerend subveld van logica is geweest.

Aan de andere kant gebruiken combinatoristen 'constructief' in een andere betekenis. Ze gebruiken het om "beter dan bruut geweld" te betekenen. De stelling van Ramsey is bijvoorbeeld niet-constructief van de POV van een combinator, omdat zijn bewijs geen betere methode biedt dan alleen de subfoto's opsommen totdat je een volledige monochromatische vindt. Aan de andere kant is het, vanuit de POV van een logicus, constructief - geef een opsomming van de subfoto's totdat je een volledige monochrome vindt! (Of nog eenvoudiger: het principe van de duiventil heeft dezelfde smaak.)

Zo:

  1. Heeft iemand naar logica gekeken waarin alleen combinatoristisch-constructieve methoden ok zijn?
  2. Zo nee, heeft iemand een formele analyse gedaan van wat 'beter dan bruut geweld' betekent? (Dit lijkt anders dan de vragen die doorgaans worden gesteld in algoritmiek, maar ik zou niet geschrokken zijn als ze er ook over hebben nagedacht.)
12
2. is hier het grootste probleem, geloof ik. Is "brute kracht min 10 gevallen die van tevoren triviaal kunnen worden uitgesloten", beter dan bruut geweld? Ik denk dat het ding dat naast je "combinatoristisch-constructieve" komt, P is (in tegenstelling tot NP).
toegevoegd de auteur James Fee, de bron

7 antwoord

U vraagt ​​naar resource-aware logica. Je zou kunnen kijken naar het werk van Sam Buss en zijn logica die verschillende complexiteitsklassen kenmerken. Er is ook een hoop werk aan de hand op impliciete karakteriseringen van complexiteitsklassen . In een andere werklijn zou je kunnen kijken naar substructurele logica, zoals lineaire logica.

Ik vermoed dat we "brute force search" kunnen karakteriseren in termen van computationele complexiteit. Als de statusruimte bijvoorbeeld van grootte $ N $ is en de zoekopdracht $ O (\ log N) $ kost, is dit waarschijnlijk geen brute kracht. Als het $ \ omega (N) $ is, dan is het waarschijnlijk brute kracht.

8
toegevoegd

dus voor alle duidelijkheid, de reden waarom de eindige versies van Ramsey's stelling en het duiventilprincipe intuïtionistisch zijn, is omdat je een expliciete gebondenheid hebt aan de zoekruimte. Als de zoekruimte a priori onbegrensd zou zijn (zoals in de oneindige versies van deze stellingen), zouden deze bewijzen het principe van Markov toepassen. Dat is het geval, om dergelijke "combinatorisch niet-constructieve" bewijzen te verbieden, ben ik er vrij zeker van dat je moet overstappen naar een ultrafinistische logica, d.w.z. het bestaan ​​van zeer grote aantallen ontkennen. Want telkens als we er een hebben, kunnen we er op doorgaan om een ​​constructieve zoektocht over een zeer grote ruimte uit te voeren.

Ik denk dat het probleem met het gebruik van de klassieke complexiteitsklassen om dit te benaderen, is dat er een P-tijd (inderdaad constante tijd) algoritme is voor het berekenen van het Ramsey-getal R (6,6), dat niet zal eindigen in de levensduur van het universum .

6
toegevoegd
Het verbieden van combinatorisch niet-constructieve bewijzen vereist niet het ontkennen van het bestaan ​​van zeer grote aantallen. Het vereist alleen een verzwakking van het inductieschema van de eerste orde Peano-rekenkunde, zodat je niet langer kunt bewijzen dat overdreven snelgroeiende functies overal worden gedefinieerd. Zie het boek van Cook en Nguyen dat ik in mijn antwoord noem.
toegevoegd de auteur Joel Brown, de bron
Nou, ik denk dat je het op die manier zou kunnen formuleren, maar ik geef het de voorkeur om het op deze manier te formuleren: je noteert een definitie van iets dat een functie zou moeten zijn op alle natuurlijke getallen, maar je kunt niet bewijzen dat het gedefinieerd is overal. Het punt is dat er geen specifiek groot aantal bestaat dat je niet kunt bewijzen. De beperking is wat u kunt bewijzen over functies die te snel groeien. Het is volledig analoog aan het feit dat de stelling van Goodstein niet te bewijzen is in PA, omdat de functie in kwestie te snel groeit. Ik zou niet willen zeggen dat PA om deze reden "ultrafinitistisch" is.
toegevoegd de auteur Joel Brown, de bron
Bedankt voor de link, en ja, misschien is het niet echt nodig om ultrafinitisme te noemen, wat geen goed gedefinieerd wiskundig concept is. Dit is een effect van een verzwakt inductie schema, nietwaar? Dat wil zeggen, het voorkomt dat u uitvoerbare bewijzen geeft van het bestaan ​​van zeer grote aantallen?
toegevoegd de auteur Noam Zeilberger, de bron

Although the question of finding explicit constructions was considered in combinatorics very early, theoretical computer science gives a fairly concrete way to say what "constructive" means. Lower bounds for Ramsey numbers is a good example. it was discussed in this MO question. Probabilistic methods shows that there are graphs with $2^{k/2}$ vertices without a complete subgraph or an empty subgraph on k vertices. Explicit constructions are constructions that can be described by a polynomial type (deterministic) algorithm. (But you can demand also a stronger requirement of log-space algorithms.) the best known explicit constructions (that can be described by a log space algorithm) gives such graphs with number of vertices proportional to $2^{k^C}$ vertices for every C>0. In combinatorics explicit constructions are usually related to derandomization. See also this post about derandomization.

Ik weet niet zeker wat de relatie is tussen logicus-constructief zoals beschreven in de vraag en expliciete constructie en derandomisatie in combinatoriek. Het lijkt erop dat ze verband houden met het begrip "effectieve en niet-effectieve" bewijzen waarbij niet-effectieve bewijzen bewijzen zijn die geen algoritme geven wat dan ook. Een beroemd niet-effectief bewijs is de uitspraak (door Nash) dat de eerste speler in een n by n HEX-game een winnende strategie heeft. (Met behulp van stelen strategie-argument.) Een ander voorbeeld van soortgelijk karakter is het argument dat er irrationals a en b zijn zodat $ a ^ b $ rationeel is. (Gebaseerd op $ (\ sqrt 2 ^ {\ sqrt 2}) ^ \ sqrt 2 = 2 $.) Ik denk dat een beroemd gebied waar effectieve bewijzen zeer wenselijk zijn, ligt in de context van verbeteringen voor Liuville's stelling betreffende trancendental. Dus misschien is het onderscheid tussen effectieve en niet-effectieve bewijzen dichter bij de logische problemen waarnaar de vraag verwijst.

5
toegevoegd
Interessante functie, maar ik denk niet dat het voorbeeld, als een voorbeeld van niet-effectief of niet-expliciet bewijs, nep is. Het is waar dat de term "niet-doeltreffend bewijs" niet altijd nauwkeurig of formeel is.
toegevoegd de auteur Pierre Spring, de bron
Wauw, dat Goldwasser/Kilian-algoritme is echt geweldig! Het "bijna altijd" snel eindigt, dat is netjes. Zijn er snelle "bijna altijd" semi-algoritmen? (Dat wil zeggen, je mag helemaal niet eindigen op "niet veel" ingangen.) De meeste semi-algoritmen die ik ken, zijn afkomstig van dingen zoals de volledigheid van de eerste-orde logica, dus hun slechtste prestaties zijn onuitsprekelijk. Zijn er algoritmen waarvan je weet dat ze snel af zijn als ze überhaupt voltooid zijn? (De reden waarom ik vraag is dat het het idee zou weerleggen dat combinatorisch constructieve methoden de intuïtionistische methoden onderverdelen.)
toegevoegd de auteur Sekhat, de bron
Neel's punt is dat "ineffectief bewijs" in de sterke zin van het verschaffen van helemaal geen algoritme mooi wordt vastgelegd door intuïtionistische logica. Bijvoorbeeld, de eindigheidsstelling van Faltings geeft geen algoritme voor het vinden van de oplossingen, en een intuïtionist drukt dit uit door te zeggen dat de oplossingsset "niet oneindig" is (in tegenstelling tot "eindig"). De vraag is, is er een vergelijkbare manier om formeel vast te leggen dat (bijvoorbeeld) het probabilistische bestaansbewijs van Ramsey-grafieken geen polytijd-constructie oplevert? Het antwoord is ja: het bewijs is niet formaliseerbaar in een bepaald systeem van begrensde rekenkunde.
toegevoegd de auteur Joel Brown, de bron
Soms gaat een constructieve beweging eenvoudigweg om zorgvuldiger aangeven wat het is dat een bewijs laat zien. In Hex kan er geen gelijkspel zijn en is het niet zo dat de tweede speler een winnende strategie heeft. Waarschijnlijk verschijnt elk cijfer even vaak in Pi. Klassiek verschijnt er minstens één oneindig vaak (eigenlijk minstens twee). Constructief lijken ze niet allemaal eindeloos. Soms volgt het volgen van die discipline eigenlijk naar sterkere bewijzen (maar dat is een onderwerp voor een andere vraag).
toegevoegd de auteur CurseStacker, de bron
Het "irrationele tot irrationele = rationele" voorbeeld is nep, zie math.andrej.com/2009/12/28/…
toegevoegd de auteur Andrej Bauer, de bron

Ik denk dat het meest in de buurt komt van wat je zoekt, zijn de logische systemen die zijn bestudeerd in de recente logische fundamenten van bewijscomplexiteit van Cook en Nguyen . Dit zijn systemen waarin de aantoonbare totale functies liggen in bepaalde goed gedefinieerde computationele complexiteitsklassen. Bestaansbewijzen in deze systemen impliceren met name dat het object waarvan het bestaan ​​wordt beweerd eenvoudig kan worden berekend.

Deze onderzoekslijn gaat minstens terug naar Buss (zoals vermeld door Andrej Bauer), die systemen van begrensde rekenkunde definieerde die nauw verwant zijn aan de niveaus van de polynomiale hiërarchie (een hiërarchie van complexiteitsklassen waarvan de laagste niveaus $ P $ en $ zijn NP $). Meer in het algemeen is het veld dat bekend staat als "bewijscomplexiteit" gewijd aan het bestuderen van de relatie tussen computationele complexiteitsklassen (in het bijzonder circuitcomplexiteitsklassen) en formele systemen voor rekenkunde met geschikt verzwakte inductie-axioma's.

Dit alles veronderstelt dat u tevreden bent met het idee dat "beter dan brute kracht" zoiets als "polytime-oplosbaar" betekent. Er zijn beperkingen met het concept van polynomiale tijdsolvabiliteit, met name de nadruk op asymptotisch gedrag en de focus op worst-case complexiteit. (Hoewel de complexiteit van de gemiddelde casus is bestudeerd, zijn de natuurlijke vragen daar heel moeilijk te beantwoorden en de theorie is veel minder ontwikkeld.) Toch zijn er veel interessante inzichten ontstaan ​​uit het bestuderen van bewijscomplexiteit en ik denk dat het een veelbelovende weg is voor verder onderzoek.

5
toegevoegd

Ik denk dat het hele onderwerp van computationele complexiteitstheorie , met de concepten P, NP, PSPACE, EXPTIME en zo verder, gaat het in essentie over het verkennen van verschillende precieze zintuigen van wat 'beter dan bruut geweld' zou kunnen betekenen.

Combinatoristen beschouwen polytijd-algoritmen bijvoorbeeld als in principe constructief, terwijl brute-kracht-algoritmen inherent exponentieel zijn. De subtiele NP-klasse laat een constructieve, maar niet-deterministische smaak toe, doordat oplossingen snel kunnen worden geverifieerd, maar moeilijk te bouwen zijn. Er is een volledige dierentuin met complexiteitslessen , waarvan de onderlinge relaties intensief worden bestudeerd in de complexiteitstheorie. (Zie ook de kinderboerderij daar, om te beginnen.)

3
toegevoegd
De subtiele verschillen die u noemt, zoals het verschil tussen de gemiddelde complexiteit van de zaak en de worst case-complexiteit, worden niet verwaarloosd en worden ook goed bestudeerd. Zie bijvoorbeeld en.wikipedia.org/wiki/Generic-case_complexity .
toegevoegd de auteur Dane O'Connor, de bron
Bijvoorbeeld, gerandomiseerde algoritmen (zie en.wikipedia.org/wiki/Randomized_algorithm ) werden ooit beschouwd als als niet-standaard, maar zijn nu volledig klassieke methoden, in vergelijking met meer esoterische huidige overwegingen, zoals kwantumberekening.
toegevoegd de auteur Dane O'Connor, de bron
Er is een overvloed aan algoritmen die in het slechtste geval dubbel exponentieel zijn en die in de praktijk vaak snel eindigen (Groebner-basen zijn het voor de hand liggende voorbeeld). Algoritmen in $ n ^ 17 $ voor zelfs gematigde n worden nooit effectief beëindigd. In de praktijk zijn de bruikbare klassen dus veel subtieler dan die waarvoor theoretici besloten hebben te studeren, IMHO. Op dezelfde manier hebben allerlei onbeslisbare problemen (grote!) Beslisbare fragmenten [zoals Halting, waarvan je weet dat het beter is dan ik].
toegevoegd de auteur Mathias711, de bron

Ik heb altijd het werk over logica overwogen waarbij normalisatie bepaalde complexiteitsklassen kenmerkt (vooral Mairson's werk over PTIME en lineaire logica ) om in deze categorie te vallen. Ik veronderstel (zoals de opmerking van Noam opmerkt) dat dit een op complexiteit gebaseerd idee is dat niet lijkt te wijzen op het begrip "beter dan brute kracht" waarnaar je op zoek bent.

1
toegevoegd

Aanpak van vraag 1: je zou willen kijken naar Paul Taylor's Abstracte Steen Dualiteit , misschien beginnend met Functies voor Computable Topology . Hij doet veel werk dat zeer constructief van aard is, en hij lijkt een heel lange weg te gaan, in wezen een hele lading van wiskunde en logica vanuit een constructieve invalshoek.

1
toegevoegd
Mijn doel met ASS is om een ​​taal te ontwikkelen die er zoveel mogelijk uitziet als "gewone wiskunde" maar die een berekenbare basis heeft in plaats van een vaste theorie. Als alleen mensen de formele definitie van berekenbaarheid hadden gekend, geloof ik dat dat de kracht was van de traditionele fundamenten voordat de verzamelingenleer meeging, en dat natuurlijke wiskunde berekenbaar is. Een lambda-calculus voor echte analyse is misschien een betere plaats om met ASS te beginnen.
De vraag is echter of ik denk aan het verschil tussen berekenbaarheid en haalbaarheid (zeg polynomiale tijd). Hoewel er resource-logica's zijn die hier over kunnen praten, zouden ze er veel meer anders uitzien dan gewone wiskunde dan ASD. Ik denk dat dit eerst op het berekenbare niveau moet worden opgelost, waarbij de haalbare versie aan een andere generatie wordt overgelaten.
toegevoegd de auteur fearphage, de bron