Top new questions this week:
|
|
Let $Q$ be a polynomial time computable graph property of simple, undirected graphs. Consider the following two optimization problems on any input graph:
P1. Find a largest induced subgraph of the ...
|
|
Let $L\subseteq \Sigma^*$ be a language of finite words and $n>0$ some integer.
I would like to know if anything is known on the time and space complexity with respect to $n$ to check for ...
|
|
What is the complexity of the following problem?
Instance: Simple, undirected graph $G$, and a positive integer $k$.
Question: Does $G$ have an induced subgraph on at least $k$ vertices, such that ...
|
|
TL;DR: I have a definition, and I'm wondering if it already has a name or has been studied.
Suppose we have a sequence of operations (or if we want to be mathematical, functions whose domains and ...
|
|
The best algorithms for the following problem has $O(n^2 \log{n})$ running time:
Given a set $P$ of $n$ points in $\mathbb{R}^2$ and a real parameter $r$, can we cover all the points in $P$ with two ...
|
|
This is my first question in this site. I ask this question since I got no comment and no answer for one year and two months in cs.stackexchange and it was automatically deleted by the system. So, ...
|
|
I'm trying to figure out what is the current knowledge about how hard it is, given a generating matrix of a linear code over a field $F_{q}$, approximate it's distance.
I of course found that ...
|
Greatest hits from previous weeks:
|
|
I am looking for the method / correct way to approach to reduce the traveling salesman problem to an instance of traveling salesman problem which satisfies the triangle inequality, ie:
$D(a, b) \leq ...
|
|
My Ph.D. is in pure mathematics, and I admit I don't know much (i.e. anything) about theoretical CS. However, I have started exploring non-academic options for my career and in introducing myself to ...
|
|
For an optimization problem $(P)$ and its dual $(D)$, I have read about two concepts: Weak Duality, and strong Duality. What I don't understand is how they are different:
Weak duality:
If $\bar{x}$ ...
|
|
What's an intuitive proof that shows that the conditions of complementary slackness are indeed true:
If $x^*_j > 0$ then the $j$-th constraint in the dual is binding.
If the $j$-th constraint in ...
|
|
In Mike and Ike's "Quantum Computation and Quantum Information", Grover's algorithm is explained in great detail. However, in the book, and in all explanations I have found online for Grover's ...
|
|
I've come across the polynomial algorithm that solves 2SAT. I've found it boggling that 2SAT is in P where all (or many others) of the SAT instances are NP-Complete. What makes this problem different? ...
|
|
Paul Erdos talked about the "Book" where God keeps the most elegant proof of each mathematical theorem. This even inspired a book (which I believe is now in its 4th edition): Proofs from the Book.
If ...
|
