Références pour les techniques de preuve TCS

38

Existe-t-il des références (en ligne ou sous forme de livre) qui organisent et discutent des théorèmes du SDC par technique de démonstration? Garey et Johnson le font pour les différents types de constructions de widgets nécessaires pour les preuves de complétude NP (en particulier dans le chapitre 3 de leur livre), mais je me demande s'il existe quelque chose qui traite les techniques de preuve dans les systèmes de caméras de télévision plus largement.

Ainsi, par exemple, les sujets pourraient inclure la diagonalisation, ventilée par type de construction utilisé; preuves par historique de calcul; constructions de tableaux; arguments d’incompressibilité, etc. Je suppose que je pourrais simplement découper une théorie standard du texte de calcul et réorganiser les sections, mais il serait bien qu’il existe quelque chose qui fournit également des commentaires supplémentaires et montre les points communs entre les techniques utilisées. utilisé.

Soyons clairs: comme tout texte utilise des preuves, ce qui m’intéresse vraiment, c’est de trouver une référence où les techniques de preuve sont elles-mêmes le sujet réel.

Outre le chapitre 3 de Garey et Johnson, voici un autre exemple partiel dont je viens de penser: dans Li et Vitanyi , au chapitre 6, ils abordent la méthode de l'incompressibilité et donnent des exemples d'application de la technique.

reference-request proof-techniques Kurt
la source
ce livre est idéal pour la complexité de calcul cs.princeton.edu/theory/complexity
Marcos Villagra
C'est une question si vaste que son champ d'application est tout ce qu'il y a dans le champ! voter pour fermer sauf si cela peut être réduit de manière significative. En outre, il est fort probable que vous ayez besoin d'un wiki de communauté, car il n'y a pas de réponse définitive.
Suresh Venkat
1
Je ne cherche pas une liste de techniques de preuve; J'espérais qu'il y avait déjà une référence de cette nature quelque part que quelqu'un pourrait m'indiquer. Pourquoi ne pas laisser cela ouvert un peu plus longtemps jusqu'à ce que davantage d'yeux aient eu l'occasion de le voir?
Kurt
5
Je ne peux pas m'empêcher de penser que je suis mal compris ici. Si la question est trop large, il devrait y avoir beaucoup de réponses possibles. Je ne connais aucune réponse directe (de toute évidence, sinon je n'aurais pas demandé), et peut-être seulement quelques réponses partielles.
Kurt
1
Le problème est que la technique de preuve dans un sous-domaine du TCS ne se poursuit généralement pas dans un autre domaine. Je pense que les mathématiciens étudient généralement des preuves dans leurs cours pour apprendre les techniques de preuve. Par exemple, la diagonalisation ne s'applique pas à la preuve d'un programme correct, alors que les invariants sont d'une utilité minime, voire nulle, dans la théorie de la calculabilité; les techniques de preuve de la complexité amortie ne concernent que ce sous-champ. La réduction est inhabituelle en ce qu'elle est appliquée à la calculabilité, à la complexité et à la cryptographie prouvable. Google "théorème gratuitement" pour une technique pertinente uniquement pour les programmes dans certaines langues.
Blaisorblade

Réponses:

36

Le compagnon de la théorie de la complexité par Hemaspaandra et Ogihara . Ce n'est pas exhaustif en termes de techniques (je suppose que ce n'est pas le cas), mais je pense qu'il peut être considéré comme une réponse à votre question. Voici les titres des chapitres:

  • La technique d'auto-réductibilité.
  • La technique de la fonction à sens unique.
  • La technique de division et de conquête du tournoi.
  • La technique d'isolement.
  • La technique de réduction des témoins.
  • La technique d'interpolation polynomiale.
  • La technique de groupe insoluble.
  • La technique de restriction aléatoire.
  • La technique polynomiale.
Joshua Grochow
la source
1
Merci! D'après le texte de l'éditeur, "... le livre est - contrairement à d'autres textes sur la complexité - organisé par technique plutôt que par sujet", cela ressemble vraiment à ce que j'avais en tête. (Je dois admettre que je ne reconnais pas beaucoup de ces titres de chapitres - ce livre sera probablement un peu dur pour moi.)
Kurt
25

Voici un autre livre où les chapitres sont plus axés sur les techniques de preuve.

"La combinatoire extrême avec des applications en informatique", de Stasys Jukna. C'est un bon livre et couvre beaucoup de combinatoires dont vous pourriez avoir besoin dans TCS. Bien entendu, le sujet n’inclut pas la diagonalisation, les tableaux, etc., mais c’est un ensemble de techniques combinatoires ordonnées recherchant une application (et à différents endroits du texte, les applications sont détaillées).

Une "première ébauche" de la deuxième édition est disponible ici .

Ryan Williams
la source
Merci, cela semble être un texte vraiment utile - je suis allé de l'avant et me suis commandé une copie.
Kurt
15

Le livre "Les pierres précieuses de l'informatique théorique" est un bon moyen d'apprendre beaucoup de techniques différentes (même si chacune d'entre elles est appliquée une seule fois):

http://www.calvin.edu/~rpruim/publications/gems/

Dave Doty
la source
Cela semble être un texte intéressant, mais je viens d'essayer de le rechercher sur Amazon ( amazon.com/Gems-Theoretical-Computer-Science-Sch%C3%B6ning/dp/… ) et j'ai dû faire une double prise! Doit être épuisé et très prisé.
Kurt
15

Il existe un wiki consacré à différentes techniques de preuve: http://www.tricki.org/ (semble être inspiré par Timothy Gowers).

ilyaraz
la source
Ah, ça a le potentiel d’être exactement ce que j’espérais. Je vois qu'ils ont des entrées réservées pour la complexité de calcul et les algorithmes, mais hélas, jusqu'à présent, ils sont vides.
Kurt
Vous pouvez améliorer ces sections, je pense.
ilyaraz
En effet, j'apprendrais probablement mieux un sujet en écrivant une nouvelle entrée qu'en lisant un sujet existant ... un bon projet à long terme, peut-être.
Kurt
13

Une autre technique utile dans de nombreux domaines de l’informatique théorique:

Noga Alon et Joel H. Spencer, La méthode probabiliste (3e édition), Wiley, ISBN 0470170204.

András Salamon
la source
12

S. Fenner, L. Fortnow, S. Kurtz et L. Li. Un toolkit du constructeur d'oracle. Information and Computation, 182 (2): 95-136, 2003. (également disponible sur la page d'accueil de Lance ).

Il s’agit essentiellement d’un document d’enquête sur l’utilisation de la généricité dans la construction «d’oracles de concepteur» (c’est-à-dire des oracles conçus pour avoir diverses propriétés). Bien que ce soit un document, je pense que cela peut être considéré comme une réponse à la question car il est axé sur la technique et ses utilisations, plutôt que sur un résultat particulier. [Mais ceci est beaucoup plus spécifique que le Complexity Theory Companion, c'est pourquoi je pensais que cela devrait figurer dans une réponse séparée.]

Joshua Grochow
la source
7

Nous avons commencé à poser des questions de référence sur cs.SE couvrant des problèmes typiques du TCS (jusqu'à présent, introductifs). Outre la pertinence générale, certaines réponses contiennent des méthodes que tous les chercheurs ne connaissent peut-être pas, par exemple:

Nous avons aussi Comment ne pas résoudre P = NP? qui est plus sur les anti-techniques.

Raphael
la source
1

Dans l'esprit des notes de Sanjeev Arora publiées par @umar, j'aime bien les notes de conférence et les exercices de Madhur Tulsiani pour son cours "Kit d'outils mathématiques" affiché sur la page Web du cours . En plus de l'excellent matériel d'Arora, ses notes couvrent bien la théorie des graphes spectraux ainsi que la méthode de mise à jour des poids multiplicatifs.

rahulmehta95
la source