YouTube video by Patio de Oro Mariachi

LANCE: You should take a break from all the AI stuff and talk about your book! BILL: I will! But it's not _my book_ its co-authored with Erik Demaine and Mohammad Hajiaghayi. The title is > Computational Intractability: A Guide to Algorithmic Lower Bounds LANCE: That sounds similar to Garey and Johnson's classic > Computers and Intractability: A Guide to the Theory of NP-Completeness BILL: Indeed. DGH is a sequel to Garey and Johnson. LANCE: But so much has happened since 1979. BILL: Yes. That's why the book is over 500 pages and still does not cover everything since 1979. LANCE: So what IS in the book? BILL: The main question that drives complexity theory (and many other fields) is the question: Given a problem, how hard is it? LANCE: Oh, You mean like P and NP! BILL: Yes, but there is more! We cover P and NP: Many problems are proven NP-complete. Some are on Puzzles and Games. _**Examples of NP-Complete Problems that you might not have heard of**_ _Disk Packing_ : Given a set of disks and a target square, can you place the disks so that they do not overlap and all of their centers lie within the square? This is Strongly NP-hard. _Mate-in-1_ : Given a position in Settlers of Catan, can the player who is about to go win? This is NP-complete _Losing Checkers_ : Given a position in Checkers, is there a move that forces your opponent to win? This is NP-complete. This is an important problem in case you play Checkers with a Wookie, see here. _Super Mario Brothers and Many other Nintendo Games:_ Given a position in the game, and a level, can the player get to that level? This is NP-complete. (There are versions that are PSPACE-complete and versions that are undecidable) **Some use the machinery developed since G & J to show lower bounds on approximation:** _VC with vertices of degree_ \\(\le 3\\): If there is a polytime \\((\frac{145}{144}-\epsilon)\\)-approx then P=NP. We have a chapter on the Unique Games Conj--uh, uh, Theorem. **We look BELOW NP: 3SUM-hardness, APSP-hardness (these are both a bit outdated), streaming algorithms, online algorithms, others.** **We look ABOVE NP: #P, ETR,** LANCE: What's ETR? BILL: Existential Theory of the Reals is the following problem: Given a sentence of the form \\((\exists x_1)(\exists x_2)\cdots(\exists x_n)[ C_1 \wedge \cdots \wedge C_k]\\) where each \\(C_i\\) is a polynomial equality or inequality in \\(x_1,\ldots,x_n\\) is this sentence, with the quantifiers going over the reals, true? Tarski proved ETR is decidable. ETR is known to be NP-hard and is thought to be harder than NP. A problem is ETR-complete if it is equivalent to ETR. This is a way to classify some problems that involve reals that were hard to classify with more traditional classes. For example, the Art Gallery Problem (how many guards do you need) is ETR-complete LANCE: What else do you have that's above NP? BILL: Poly Hierarchy, PSPACE, and even undecidability. LANCE: Are there really NEW results about undecidability? BILL: There are some video games where questions about winning are undecidable. I doubt Turing knew that. One of them is called braid (see here). LANCE: Don't you have whole chapters devoted to the now-defunct Exponential Time Hypothesis and the 3-SUM conjecture? Bill: Also the APSP conjecture. Are these now-defunct conjectures still worth studying? I did a blog post on that here. Do you read my blog posts? LANCE: Do you read mine? BILL: Fair point. LANCE: Despite having three chapters obsolete, the rest of the book sounds great. Where can I get it? BILL: You can buy it on Amazon, see here. You can buy it at MIT press here. You can download a prior draft here. By gasarch

Une application en ligne pour créer des murs multimédias collaboratifs proposée par La Digitale

ALT: The Fog: Eerie Ghosts Emerge

Une application en ligne pour créer des murs multimédias collaboratifs proposée par La Digitale