The future of parameterized complexity: truly linear time FPT and the WQO hybrid hardware model

In this paper we share new ideas and programmatic perspectives that emerged from our Alexander von Humboldt travels during that period around the University of Bergen event (Google “Mikefest Bergen”). These are developing nicely in papers that will soon appear, developed from our fresh ideas that are briefly described here. Besides Bergen and AvHS, we also thank Dagstuhl, which hosted us for a wonderfully mind-stretching workshop focused on applications of modern computing. The key new ideas/perspectives/directions are: (1) Big Data is here to stay. For parameterized complexity, centered on the notion of FPT, that is, solvability in time f(k)⋅n^c the focus must shift to truly linear time FPT (TLFPT) which permits time-costs of O(n)+f(k). This is a central new game. And, it seems to be fascinating. (2) Worst-case analysis of algorithms is largely over. That’s not how AI works. The new game is encountered obstructions and learning algorithms. There is a big future, we believe, in problem-specific well-quasi-ordering (WQO), as introduced in our paper for Hans Bodlaender’s 60th Festschrift. A potent analogy to Physics has come into focus during this period, and will be explained with key references. (3) Practitioners care about runtimes. And, practical computing has moved to models called hybrid hardware where most time costs are accounted for in a sequential model, but specialized parallel hardware can be invoked. We propose to consider TLFPT* where “magical” parallel hardware (perhaps partly quantum) can make h(k) order tests in a problem-specific WQO as a “Big OR” which can be called for the timecost of a single order test. Because of the algebraic structure of WQOs, there is hope for quantum hardware to deliver enough for a sufficiently large h(k) in parallel order tests, for practical purposes.