28
As already stated in the comments, it depends on the definitions, as usual. My attempt to answer this needs quite a few definitions, so this will be another example of my inability to give concise answers.
Definition: An optimization problem is a tuple $(X,F,Z,\odot)$ with
$X$ the set of suitably encoded (strings) instances or inputs.
$F$ is a function ...
13
If you keep track of the 2 smallest elements you have seen so far as you traverse the array, then you only need to go through the array once, and for each element you compare to the larger of the 2 current smallest and if the new element is smaller, then you replace the larger of the 2 current smallest with the new element. This requires only a few ...
11
So it seems you are intrigued about the relationship between the informedness of a heuristic function and its pruning power.
This is a well-known relationship established in the literature from the 80s (see for example Pearl, Judea. Heuristics, Addison-Wesley, 1984 who, by the way, has been awarded this year with the Alan Turing award).
As you already ...
9
No. Just knowing the size of the search space is not enough to tell whether GA will work or not. It also depends on the objective function (the "shape" of it), e.g., whether it is smoothly varying or not, how many local minima it has, and so on.
There is no good theory to know whether GA will work or not. Ultimately, all you can do is try it and see.
As ...
8
Since TSP is NP-complete, most problems you'll encounter in practice can be. (NP is a pretty general class.) A classic paper of Karp gives a large number of other NP-complete problems that, by definition, can be reduced to TSP.
8
If you have only one life only safe way is to check every element starting from minimal. It's $O(n)$
If you have two lives and limited with $k + 1$ comparisons the minimal element of array you can check first has index $k$, so we still have $k$ comparisons to check all previous elements one by one, if no lives was lost than next element to check has index $...
8
Here's an alternative way of viewing D.W.'s hint. Using the formula $\sum_{i=1}^m i = \frac{(m+1)m}{2}$,
$$ \sum_{i=a+1}^b i = \sum_{i=1}^b i - \sum_{i=1}^a i = \frac{b^2+b}{2} - \frac{a^2+a}{2} = \frac{(b-a)(b+a+1)}{2}. $$
Given a factorization $2n = xy$, we can solve the system $x = b-a$, $y = b+a+1$. The result is $b = (y+x-1)/2$, $a = (y-x-1)/2$. So we ...
8
Consider the following set of $n$ orders, which I give for $n = 6$:
$$
123456 \\
213456 \\
132456 \\
124356 \\
123546 \\
123465
$$
Hopefully the generalization to arbitrary $n$ is clear.
If you never compare $i$ and $i+1$ then you cannot tell apart permutation $1$ from permutation $i+1$. This means that you need at least $n-1$ comparisons (this is not an ...
7
Here's a hint: if $n$ can be represented as the sum of $2k+1$ consecutive integers, and if the middle of those consecutive integers is $m$, then what can you say about the relationship between $n$, $k$, and $m$? Now, given $n$, can you determine whether it is expressible as the sum of an odd number of consecutive integers?
7
You are right that NP-completeness applies only to decision problems. What they mean by "Problem 2.1 is NP-complete" can be either
The decision problem corresponding to Problem 2.1 is NP-complete
or
The decision problem corresponding to Problem 2.1 is NP-complete, and the search problem is in FNP
Here the search problem is finding a clique of size $k$...
7
The Birkhoff–von Neumann theorem states that a doubly stochastic matrix (a matrix with non-negative entries in which rows and columns sum to 1) can be written as a convex combination of permutation matrices (0/1 matrices which contain precisely one 1 in each row and column). This immediately implies your result.
If you don't want to assume this theorem, you ...
7
No. The optimization problem is "How big is the biggest $X$?" and the decision problem is "Is there an $X$ that is bigger than $y$?" Solving the decision problem simply involves comparing $y$ with the size of the biggest $X$. You can certainly compare two numbers in polynomial time so, if you can solve the optimization problem (compute ...
6
From the information you give in your question, I can not see how to apply standard optimisation methods (that I know of). Your objects are not that complicated (more on that later) but your target function is a nasty one: its values are defined by an external system out of your control, it is unlikely to have any nice properties, and so on. Therefore, I ...
6
A decision variant of the problem might be:
Does there exist a configuration of the system such that the objective function assumes a value less than or equal to $y_0$?
It depends entirely upon the form of the objective function. Suppose that the objective function is constant, i.e., $f(x) = c$. Then a constant-time algorithm which solves the decision ...
6
TFNP is the class of multivalued functions with values that are polynomially verified and guaranteed to exist.
There exists a problem in TFNP that is FNP-complete if and only if NP = co-NP, see Theorem 2.1 in:
Nimrod Megiddo and Christos H. Papadimitriou. 1991. On total functions, existence theorems and computational complexity. Theor. Comput. Sci. 81, 2 (...
6
No. You can't do better than $\Theta(n^2)$ in the worst case.
Consider an arrangement of points where every pair of points are at distance $1$ from each other. (This is a possible configuration.) Then you can't do better than to examine every edge. In particular, if there is any edge you have not examined, then an adversary could choose the length of ...
6
The optimal number of comparisons (not necessarily the fastest one) goes like this for $n = 2^k$:
Compare $a_1$ and $a_2$, $a_3$ and $a_4$, and so on. Store only the smallest of each pair in a list $b_1,\ldots,b_{n/2}$.
Repeat $k-1$ more times to get the minimum $a_{\min}$.
Let $L$ be the set of all $k$ elements which were compared to $a_{\min}$ and were ...
6
The problem you're trying to solve is exactly graph connectivity. You don't necessarily need to construct the graph explicitly but this is a graph problem.
By "you don't necessarily need to construct the graph explicitly", I mean that you don't necessarily need to create any new data structures. Every time your graph algorithm says "vertex", you can think "...
6
Reduction from 3-SAT:
a variable in 3-SAT becomes a character in your problem and is paired with its negation. Each clause becomes a word.
e.g.
3 SAT: (a,b,-c) && (-b,c) =>
pairs: (a,-a), (b,-b), (c,-c).
words: (a,b,-c), (-b,c)
Selecting a character in your problem means setting that literal to true in the 3-SAT instance. The corresponding ...
5
¡Nice question really!
The book is right and it just suffices for the path cost to be a nondecreasing function of the depth of the node ---though an additional note should be posted, see below. This directly implies that it is not necessary for nodes in the same level to have the same cost. Truth, however, is that it is hard to find such an example because ...
5
The shortest path may indeed change. This is not because of some property of the uniform cost search, but rather, the property of the graph itself. Note that adding a constant positive cost to each edge affects more severely the paths with more edges. Here is an example, where the shortest path has cost $5$:
Adding a cost of $1$ to each edge changes the ...
5
As the comments say, the answer depends on the exact definitions.
Let me interpret the question in a very basic (even naïve) way.
Let $S$ be some relation, that is $S \subseteq \{ (a,b) \mid a,b \in \Sigma^*\}$.
Now we define a search problem for $S$:
Given $a$, find a $b$ such that $(a,b) \in S$.
and a decision problem for $S$:
Given $(a,b)$ ...
5
You are correct: it's $\Theta(n)$ in the worst case. Suppose you're looking for something that's no bigger than the smallest value in a max-heap. The max-heap property (that the value of every node is at least as big as everything in the subtree below it) gives you no useful information and you must check both subtrees of every node.
5
The answer to both of your questions is yes! Definitely, even though in the worst-case you will have to enumerate the whole search space with brute-force (to prove there is no solution), it absolutely makes sense to consider how you traverse the search space. In general, you will find a lot of literature and discussion on the topic from the field of AI, and ...
5
There's a linear-time algorithm for this problem. Find the index $j$ that maximizes the ratio $r_j = a_{1j} / a_{2j}$. This $r_j$ is the maximum possible value of the ratio of sums.
Proof: The ratio of sums can be made $\ge c$ if and only if there exists a set $S$ such that $\sum_{j \in S} a_{1j} - c a_{2j} \ge 0$. That's possible iff there exists $j$ ...
5
Your problem is NP-hard. It is an easy proof In fact, it is NP-complete because we can reduce it to SAT in polynomial time
We reduce 3-SAT to your problem.
We have a lever for each variable and a bomb for each clause, the red cables are connected to clauses/bombs that have positive literals belonging to that variable/lever and the green cables are ...
4
You can use the Voronoi diagram, together with Kirkpatrick's data structure to solve this problem.
Like Raphael and Syzygy suggested, you can use Fortune's (sweepline) algorithm to create the Voronoi diagram. Worst case time: $\mathcal{O}(n \log n)$.
The Voronoi diagram will have a bunch of polygons, each one containing a transmitter. Any point within the ...
4
If the relation $R$ lies in the complexity class P (or even BPP), then boosting works by running your algorithm many times, and testing whether its output satisfies $R$. When $x \in S$, this fails with probability $\mu^N$, where $N$ is the number of times you run $A$. When $x \notin S$, this never fails. This way you can boost $\mu$ from $1-1/\mathrm{poly}(n)...
4
Here's a $O(\sqrt n)$ algorithm. We want to find all length-$k$ expressions for which
$$
n=a+(a+1)+(a+2)+\cdots+(a+(k-1))
$$
Rearranging terms, we require
$$
n=\sum_{i=0}^{k-1}(a+i) = \sum_{i=0}^{k-1}a+\sum_{i=0}^{k-1}i=ka+\frac{k(k-1)}{2}
$$
and so we must have
$$
n=k\left(\frac{2a+k-1}{2}\right)
$$
for some $a$ and $k$. If $k$ is even we require
$$
n=\left(...
Only top voted, non community-wiki answers of a minimum length are eligible
