Research

Downward Collapses and Query Order

Everyone knows that it makes more sense to first look up in your online date book the date of the yearly Computational Complexity conference and then phone your travel agent to get tickets, as opposed to first phoning your travel agent (without knowing the date) and then consulting your online date book to find the date. In real life, order matters. This project seeks to determine whether one's everyday-life intuition that order matters carries over to complexity theory. It also seeks to find cases where collapsing powerful classes induces collapses in their weaker cousins.