Résumé - Récursivité autodécrivant vers le bas dans l'hiérarchie polynomiale des fonctions totales

Récursivité autodécrivant vers le bas dans l'hiérarchie polynomiale des fonctions totales

2025-07-25 09:45:36

{"Karthik Gajulapalli","Surendra Ghentiyala","Zeyong Li","Sidhant Saraogi"}

{cs.CC,cs.DS}

Ce document explore le concept de réduction auto-inverseible vers le bas (d.s.r.) dans le contexte de l'hiérarchie polynomiale totale (TFPH), une généralisation de l'hiérarchie polynomiale pour les problèmes de recherche totale. Les auteurs démontrent que le d.s.r. est un outil puissant pour classer les problèmes au sein de la TFPH et offre de nouvelles perspectives sur la complexité de divers problèmes. **Points clés** : * **Réduction auto-inverseible vers le bas** : Un problème est réductible vers le bas si un algorithme efficace peut le résoudre en interrogeant uniquement des instances plus petites du problème. Ce concept a été bien étudié pour les problèmes de décision, où il implique que le problème se situe dans PSPACE. * **TFPH et d.s.r.** : Les auteurs étendent l'étude du d.s.r. à la TFPH, qui inclut les problèmes avec des solutions vérifiables efficacement. Ils montrent que tout problème dans TFΣPi qui permet une réduction auto-inverseible aléatoire avec accès à une oracle ΣPi−1 doit être dans PLSΣi−1, et si le problème a des solutions essentiellement uniques, il se situe dans UEOPLΣi−1. * **Applications** : * **Évitement de gamme et principe d'ordre linéaire** : Les auteurs montrent que ces problèmes sont tous dans UEOPLNP, une sous-classe petite de TFΣP2. Ce résultat fournit de nouveaux bornes supérieures pour ces problèmes et a des implications pour les constructions explicites d'objets combinatoires tels que les matrices rigides et les tables de vérité difficiles. * **Problème du roi** : Les auteurs démontrent que le problème du roi, un problème candidat dans TFΣP3 qui n'a pas été montré pour s'effondrer dans une sous-classe plus petite, s'effondre en réalité dans PLSΣ2. Ils fournissent également un algorithme ZPPΣ2 pour le roi, réfutant des conjectures précédentes sur sa complexité. * **Preuves alternatives** : Les auteurs utilisent le cadre du d.s.r. pour fournir des preuves alternatives pour plusieurs problèmes importants, y compris le problème de complémentarité linéaire des matrices P, les jeux de parité, les points fixes de Tarski et le problème S-Arrival. Ces preuves sont plus courtes, plus simples et plus algorithmiques que les preuves existantes. * **Limites** : Les auteurs mettent également en lumière les limites du d.s.r. en tant que cadre pour l'appartenance à PLS. Ils montrent que sauf si FP=PLS, il existe un problème PLS-complet qui n'est pas d.s.r., indiquant que le d.s.r. traditionnel n'est pas un cadre complet pour PLS. **Signification** : Ce document fournit une étude complète du d.s.r. dans la TFPH et démontre son pouvoir pour classer les problèmes et fournir de nouvelles perspectives sur leur complexité. Les résultats ont des implications pour divers domaines de la théorie de la complexité, y compris les problèmes de recherche totale, les constructions explicites et l'hiérarchie polynomiale.