APX Complete

This NP-complete stuff is interesting. While I got some of it 30 years ago in undergrad, this is the first time I've looked at it from a truly abstract view. I can see why the theorists like it so much. That said, I learned long ago that I am a better engineer than philosopher, so I'll try not to go too deep down the rabbit hole.

Continuing the thought of a general-purpose NP-Complete solver. What we're really looking at is the class of APX problems; the set of NP problems that can be approximated in polynomial time. Note that the approximation bound is not arbitrary. Such a problem falls into the (presumably) broader set of PTAS (Polynomial Time Approximation Scheme) which states that you can get as close as you want as long as you're OK with not being spot on. Assuming the generally held (but unproven) conjecture that P is a proper subset of NP is true, than PTAS is a subset of APX.

I'm more interested in APX. I don't mind the approximation bound being fixed some distance from perfect. However, I'd loosen the definition just a bit by relaxing the constraint of guaranteed performance. Instead, I'd like to say that for an arbitrary bound, and alpha-risk, the probability that the algorithm produces a result which deviates from the optimal solution by more than the bound is 1 minus the alpha risk.

Before even getting to the assertion, some technical details need to be worked out. First and foremost, are any of the problems I'm considering really NP-Complete? They may just be polynomial time with unacceptably large exponents. Finding a reduction from a known NP-Complete problem may not be a trivial task (and may not even exist). I'm pretty sure I can find something to work with; but it may not be the set of problems I started with.

Next is the problem of guaranteeing the alpha-risk, which is, frankly, something more suited to frequentist methods. Finding a neutral prior, or showing that a biased prior still offers proper coverage, could also get mired in unpleasant complications.

Finally there's the issue at hand: can the risk be guaranteed in polynomial time? I actually think this will be the most straightforward part of the argument. Most algorithms that aren't insane are polynomial time and proving as much isn't that difficult. I either find a method that works or I don't.

This seems like solid dissertation stuff to me. Not sure if my advisor will agree, but it's an idea I'm going to hold onto for at least a while. Plenty of time to adjust things.