Comment trouver une idée non triviale en informatique théorique?

Je suis un doctorant travaillant en informatique théorique. J'ai lu les articles de recherche de nombreux chercheurs et j'ai vu de nombreux outils et mathématiques qu'ils utilisent pour concevoir un algorithme. Par exemple, voir ce document de recherche [Primality in P] . Je ne dirais pas que ce document de recherche est basé sur une ou deux idées, mais il est basé sur de nombreuses idées qui nécessitent des mathématiques sérieuses. J'ai du mal à trouver ce genre d'idées de quelques années. J'ai travaillé sur un problème pendant plusieurs mois, mais rien de non trivial ne me vient à l'esprit. Toutes les idées qui me sont venues à l'esprit jusqu'à présent sont triviales et très peu utiles aux chercheurs théoriques en informatique. Je me demande comment trouver une machine qui me permettra de générer des résultats non triviaux.

Question: Comment trouver une idée non triviale en informatique théorique? Je sais que le mot «idée non triviale» a différentes significations. Pour moi, c'est quelque chose de publiable et intéressant pour la communauté théorique de l'informatique. J'ai vu des articles de recherche dans lesquels ils définissent quelques termes (mathématiques) puis conçoivent l'algorithme en utilisant les termes définis. Je me demande comment trouver de telles choses.

Un conseil que j'ai reçu de mes amis de recherche et de mes aînés est de lire attentivement les articles de recherche et de lire très attentivement les mathématiques (théorèmes et preuves), d'essayer de faire les preuves par vous-même et de les étendre.

1. Il existe presque certainement des listes de problèmes ouverts dans votre sous-domaine particulier. Trouvez-les et lisez-les. Bien qu'il soit peu probable que vous puissiez résoudre ces problèmes --- au moins tout de suite ---, utilisez-les comme point de départ. Pouvez-vous résoudre certains cas particuliers? Pouvez-vous résoudre un problème moins général? Pouvez-vous montrer qu'un problème plus général est difficile à calculer?

2. Lisez ce que font les autres. Cela signifie faire une liste des conférences et des revues dans votre région et consacrer au moins une heure par jour à y lire des articles. Il n'est pas nécessaire de tout comprendre à la fois. Essayez de vous familiariser avec les thèmes généraux, puis choisissez un ou deux articles qui semblent intéressants ou fondamentaux et plongez-vous en eux. Étudiez les techniques et les preuves. Pouvez-vous les appliquer à des problèmes similaires ou connexes? Élaborez des exemples spécifiques en détail, dans la mesure du possible.

3. Lorsque vous lisez un résultat, demandez-vous: toutes les hypothèses sont-elles nécessaires? Et si les hypothèses étaient affaiblies ou renforcées? Les limites sont-elles vraiment optimales? Si seule une borne supérieure est prouvée, pouvez-vous prouver une borne inférieure correspondante?

Je vais essayer de répondre à cela avec mon expérience limitée. Avertissement Je ne suis moi-même qu'un doctorant senior.

La question que vous posez n'est en aucun cas insignifiante et vous n'êtes pas le seul à vous y poser des questions. Tous les doctorants, dans presque tous les domaines, qui nous ont précédés et qui nous succéderont, se demandent / se demandent la même chose. Donc, comme premier conseil: si vous vous sentez perdu, vous n'êtes pas seul!

Mon parcours académique m'a amené à croire une opinion quelque peu impopulaire; un conseiller expérimenté peut être suffisant mais n'est pas un ingrédient nécessaire dans ce processus. Assurément, avoir quelqu'un pour vous présenter progressivement un domaine avec des questions et des tâches de difficulté croissante, et fournir un soutien et des conseils suffisants tout au long du processus peut aider à formuler vos propres questions. Bien sûr, dans la plupart des cas, cela échappe à notre contrôle.

Cependant, je pense que ce n'est pas nécessaire. Certaines des premières idées et résultats originaux que j'ai obtenus sont le fruit de discussions sur des problèmes et des concepts avec d'autres doctorants de mon groupe. Faire rebondir des idées d'avant en arrière, assister à des conférences toutes ensemble et discuter des présentations et des résultats, avoir des "séminaires théoriques" hebdomadaires, etc. Pour moi, le groupe de vos collègues doctorants est presque aussi important que les conseillers eux-mêmes. Mais encore une fois, c'est un paramètre de votre environnement et pas nécessairement sous votre contrôle.

Alors, que contrôlez-vous? Je pense que la plus grande valeur-temps si vous êtes coincé dans le no-mans land, c'est de lire. Des articles consensuels les plus influents de votre région aux sondages et résultats récents. Si vous en avez l'occasion, continuez à vous appuyer sur cette image dans votre tête de ce à quoi ressemble votre région; quels sont les plus grands défis, quels sont les outils les plus précieux, qui sont les personnes clés dont vous devez suivre le travail. C'est un processus lent et fastidieux et vous devez lire beaucoup d'articles, parfois même pour identifier les plus influents, mais faites-le. Assurez-vous de lire les articles à votre propre rythme, mais comme vos pairs vous l'ont conseillé, assurez-vous de les comprendre (oui, cela inclut - par définition - les théorèmes et les preuves). Une fois que vous aurez lu suffisamment de papiers et peint votre image ornée, vous commencerez à remarquer le petit, et au fur et à mesure que vous avancerez, des "trous" plus grands que vous pourrez lentement remplir avec vos questions et, espérons-le, des réponses.

Enfin, comme vous le dira toute personne qui a écrit un article, vous ne commencez pas par magie à écrire un article. L'ensemble du processus est le produit de beaucoup de lecture, de beaucoup d'essais et d'erreurs, et de beaucoup d'écriture et d'édition. Moi aussi, je me suis senti parfois dépassé en lisant un article et je me suis vraiment demandé comment, ou même si, je pourrais jamais arriver à un résultat de la même qualité, mais ne pense pas de cette façon. Commencez petit et continuez. N'oubliez pas que lorsque vous lisez un article et que vous vous sentez intimidé, vous consommez, en quelques minutes , un travail qui a probablement été produit sur des centaines et des centaines d'heures .

Je suis désolé, je ne connais pas grand-chose à votre domaine, donc je ne peux pas donner de conseils spécifiques, mais ce sont mes pensées. Veuillez les prendre avec un grain de sel, car je pense que nous sommes sur le même bateau. Bonne chance!

Voici une suggestion: recherchez les problèmes ouverts dans votre domaine qui vous intéressent. Essayez de reformuler le problème dans différentes représentations, en particulier celles non standard. Essayez de combiner différentes idées, théorèmes et résultats de différents domaines connexes pour créer des outils pour attaquer votre problème. Formuler des conjectures et essayer de les prouver (ou concevoir un algorithme et prouver son exactitude).

C'est une question générique, je vais donc donner une réponse générique: parlez avec votre conseiller pédagogique! Vous en avez un, non? Connaissez-vous ses projets de recherche? Est-ce que l'un d'eux vous intéresse? Si aucun ne le fait, vous devriez peut-être chercher un autre conseiller ...