Saint's Log

Complexity Theory Research July 2024

Isomorphisms of Complexity Classes

Reading Reductions among polynomial isomorphism types is my first exposure to the concept of order types. More specifically, that paper proves this:

every polynomial many-one degree either consists of a single polynomial isomorphism type or else contains a collection of isomorphism types which has, under one-one, size-increasing, polynomially invertible reductions, the order type of the rationals.

Reductions among polynomial isomorphism types

P versus NP

I was telling my advisor that reading of these old papers makes me suspect that we are a very long way away from resolving the P vs NP question – we don’t appear to have made significant progress in this journey over the past few decades. This is obviously an uninformed gut feeling, not a scientific observation. I asked how researchers that have been at this for decades feel about the problem and these are some of the videos he shared. The speakers in this discussion on P vs NP covers issues such as:

1. how to go from worst case to average case complexity of hard problems
2. how to generate hard instances (with distinctions between puzzles and problems coming up in applications like cryptography)
3. whether quantum mechanics can actually solve hard computational problems (with pessimism arising from potential inability to measure the results of parallel exploration). A naive approach will not work. Shor used the structure of the factoring problem. Does that structure exist in NP complete problems?
4. whether current accepted axioms are not sufficient to resolve the problem.

There is also advice from Ron Fagin to spend some time (e.g. a couple of days each year) thinking about the hardest problem in their field. One of the most interesting questions to me was the one asking “what’s the most remarkable false proof of P vs NP proofs that you have come across“. Ron Fagin mentions the proof attempt by Vinay Deolalikar from HP Labs. This was addressed by Scott Aaronson in his post on Eight Signs A Claimed P≠NP Proof Is Wrong (scottaaronson.blog). The other comment (by Christos Papadimitriou) was about how some failed attempts have led to barriers showing that certain approaches will not work. Ron Fagin also recommends looking at the P-versus-NP page (tue.nl).

Avi Wigderson’s talk on P vs NP got me to review the List of undecidable problems – Wikipedia (he specifically mentioned Hilbert’s tenth problem – Wikipedia).

Prefix-free Sets

One of the topics I have been learning about requires an understanding of prefix sets. Prefix-free Kolmogorov complexity is one of these areas. Some resources on this subject include:

1. Lance Fortnow’s Kolmogorov complexity paper (kaikoura.pdf)
2. Why don’t prefix-free Turing machines suffer from complexity dips? – Computer Science Stack Exchange
3. computability – Construction of a universal prefix-free Turing machine – Mathematics Stack Exchange

I watched lecture 42 Kraft’s inequality (youtube.com) to get the basic idea behind Krafts inequality. The simpler proof was the one mapping prefix free codes subintervals of (0,1). Fortnow’s paper described these as intervals of real numbers whose dyadic expansion begins with 0.x for strings x in a prefix-free set A.

Error Correcting Codes

The XOR lemma used for worst case to average case hardness transformation has always seemed a bit mysterious to me. I had decided to dig into error correcting codes to better understand the list decoding approach to hardness amplification in the Pseudorandom Generators without the XOR Lemma paper. I started on this series last month and have found it extremely beneficial. It’s been much easier to read Venkatesan Guruswami’s List Decoding of Error-Correcting Codes thesis after going through this lecture series.