New answers tagged

1

If $(P_1, P_2)$ is a partition of $P$, that means that $P_2 = P\setminus P_1$. That means that is suffices to count the number of possible choices of $P_1$, which is the cardinal of the powerset of $P$, $|\mathcal{P}(P)| = 2^{|P|}$. If $P_1$ and $P_2$ have symmetrical roles, you can divide the result by $2$ (but it does not change the asymptotical complexity)...


1

You can solve the second task with $O(n)$ expected running time (average-case running time), if you use a hash table with a 2-universal hash function. As far as I know, no deterministic $O(n)$-time algorithm is known.


-1

Statement Frequency Count int i=0,j 1 while(j<=(i+1)) n+1 a=a*a n j++ n i++ 1 f(n) = 3n+3 = Time Complexity Degree is O(n) Space: a = n i = 1 j = 1 S(n) = n+1 = Space Complexity Degree is O(n)


2

For the first task you can use a solution similar to yours. Let the input array be $A[1, \dots n]$. Create an array $B$ indexed with the integers from $10$ to $10n$ where each entry is a boolean value initially set to false. Then, for each input element $A[i]$, set $B[A[i]]$ to true. At the end of the above loop, return the number of indices $y$ such that $B[...


3

If you want to write $N$ words of output, it takes at least $N$ steps of computation to do that. So, if you need to produce an exponential-sized output, you'll need to spend exponential time to do it. For that reason, a polynomial-time reduction cannot produce an exponential-sized output when run on a polynomial-sized input.


2

The fact that the given reduction takes exponential space implies it must take exponential time and therefore is not polynomial. Using Cook-Levin on a NP-complete problem does not produce an exponential-sized output; it produces a polynomial-time circuit. It constructs a circuit whose size is polynomial in the number of steps taken by the NP-verifier; since ...


2

Clearly, $\log(\frac{n}{\log(n)}) \le \log(n)$. Substitute this into the equation to get that $T=O(n)+\frac{n}{\log(n)}\left(\log\left(\frac{n}{\log(n)}\right)\right)\le O(n)+\frac{n}{\log(n)} \log(n)=O(n)+n=O(n)$ So $T=O(n)$, and indeed it is not bigger than linear time.


0

$n=|V|$, and $\sum_{v\in V}deg(v) = 2\cdot |E| = 2m$ (each edge is counted exactly twice). Take a look here for a proof why ${n \choose k} = \Theta(n^k)$ for a fixed $k$. Substitute everything, and get that also $O(n^k*m)$ is a valid estimate (again, only if $k$ is a fixed number!). c) Is clearly not a tight bound, since it doesn't even depend on $k$ (...


3

Yes. For example, let $h=\sqrt{fg}$, assuming $f$ and $g$ are positive. If not, we can let $h(x)=\max(\sqrt{|f(x)g(x)|}, g(x)/(|x|+1))$. The term, $g(x)/(|x|+1)$ makes sure that $h(x)$ will stay positive eventually. Exercise. For each two functions $f$ and $g$, where $f \in \omega(g)$, there exists a function $h$ where $f \in \omega(h)$ and $h \in \omega(g)$...


2

The answer by nir shahar goes to the point. Another way to see this is to consider Radó's non-computable function $S(n)$ (the maximum number of steps a Turing machine with $n$ states does when started with an empty tape before halting). If you could compute your function $M$, you could compute $S$ (for each TM of $n$ states compute your function $M$, run the ...


2

In the worst case, it has to be $n \cdot d$: You must check $d$ symbols of each of the $n$ strings to confirm they all start with the prefix, if you leave any out it might be different. This is essentially an adversarial argument. You certainly can speed it up for non-matching strings, like comparing lengths, just check some positions to rule out prefixes. ...


2

You are right in that to check membership (or to retrieve) using a hash function, you also need to check that the retrieved element is equal to the element in question. For a string, you should assume that this takes time linear in the length. Hence checking membership in a hash set is indeed expected $O(m)$.


2

I think this is correct and incorrect at the same time. It depends on how we define the problem we want to solve. Formulation I If we are interested in an algorithm that given $\langle M, w\rangle$ will tell you how much time $M$ runs on $w$ (assuming it halts), then there is such an algorithm: emulate $M$ on $w$ and count the number of steps it does until ...


0

It is possible that an algorithm gathers information when it's running and doesn't throw it away. If gathering that information takes O(n^2) but solving the problem with the help of the information gathered only takes O(n), then solving the same problem k times could run in O(n^2 + kn). All depends on your algorithm.


0

Recall that in a suffix tree for $T$, each leaf corresponds to a suffix of $T$, and is labeled by its position. Furthermore, each internal vertex corresponds to a common prefix of some suffixes of $T$. We label each internal vertex with the minimal position of a suffix covered by it. Construct a suffix tree for $T$, and augment it by labeling the internal ...


0

Using radix sort, the second subarray can be sorted in $\Theta(log_{b}(n\sqrt n)(n + b)$ where $b$ is the base with which the numbers are represented. If $n$ is chosen as the base, radix sort sort the array in $\Theta(log_{n}(n\sqrt n)(n + n)) = \Theta(\frac{3}{2}(n + n)) = \Theta(n)$. Now all 3 subarrays can be sorted in $\Theta(n)$ thus the array is ...


2

The other answers are correct, but f I may add an observation: it seems like you are conflating classes of problems and particular instances. There are a number of instances that can be solved in polynomial time in classes that are NP-hard in general. For instance, Boolean satisfiability is NP-hard in general, since it reduces to 3SAT. However, there are a ...


5

If the answer to the first question were to be yes, then $P=NP$, as stated in nir shahar's answer. This has not been done. "The easiest NP hard problem" However you next asked if any NP-hard problems have been solved in close to polynomial time, for which you might love to learn about what has been called "The easiest NP hard problem" ...


4

Strictly speaking, as the other answers explain, no. A polynomial-time algorithm for an NP-hard problem is not known nor expected to exist. But I think your underlying question is whether or not there are examples of natural NP-hard problems that are, in some sense, easier to solve than some other NP-hard problems. There are several flavors in which you can ...


10

By definition, if you were to find a polynomial time algorithm for an NP-hard (or NP-complete) problem, then $P=NP$. So, short answer is - no. However, its possible to think instead of solving the problems fully, to approximate a solution, or to solve them randomly. There are attempts at attacking from those points of view, but they are not perfect at all. ...


1

Let $\ell_{i}$ denote the number of digits in $a[i]$. Then the complexity of the naive algorithm as suggested by you is $O(\ell)$, where $\ell = \sum_{i = 1}^{n} \ell_{i}$. Moreover, the algorithm must visit every digit at least once. For the sake of contradiction, suppose the algorithm did not visit some digit in the array. Then an adversary can modify the ...


3

You can use the following identities: $$ (\ln n)^a \le n^\beta \iff \ln (\ln n)^a \le \ln n^\beta \iff a \ln \ln n \le \beta \ln n. $$ This is trivial if $\alpha \le 0$, so we consider the case $\alpha > 0$. For simplicity substitute $t= \ln \ln n$ and $\gamma = \frac{\alpha}{\beta}$. Notice that $\gamma \ge 0$. We obtain: $ \gamma t \le e^t \iff \gamma ...


3

You can naively compute ALL-SAT in $2^npoly(n,m)$ time, where $n$ is the number of variables and $m$ is the number of clauses. You clearly need $\Omega(2^n)$ time in the worst case just to write down the assignments (in the case of a tautology). If the strong exponential time hypothesis (SETH) holds, then this is not much harder than SAT itself, so under ...


-1

Your “algorithm” runs in O(log n) time. The function that it calculates is O(n^2).


1

Your recurrence can be written as: $ T(n) = T(n/2) + f(n) $, where $f(n) \in \Theta(n^2)$. Then, by case 3 of the Master theorem, you have $T(n)=\Theta(n^2)$. This means that you won't be able to prove a lower bound of $\Omega(n^2 \log n)$.


2

The dynamic programming algorithm goes over all subsets of $[3k]$ whose size is a multiple of 3, in nondecreasing order of size. For each such non-empty subset, it goes over all $O(n^3)$ triplets of vertices, and for each one, it performs a single table look-up. Therefore the running time is $O^*(2^{3k} n^3)$, where $O^*$ hides $\operatorname{poly}(k)$ ...


0

Your problem isn’t calculating gcd’s, your problem is the number of pairs you need to examine. If your algorithm isn’t clever then given some x, you’ll have to examine all y whether they are connected. This will take O(n) for each x. Throw out all x > n and x <= g first. Factorise each x. Find all prime factors p with the property “x has a factor > ...


2

It is NP-Hard as others have said, but... sometimes there is an easier way to solve it. You can do a Lagrangian relaxation to essentially remove the NP-hardness solve that problem, and then use that as an initial guess for the original problem. Pekny and Miller essentially did something like to for the Asymmetric Traveling Salesman problem. They reduced it ...


0

At a minimum, whenever you check successfully that x and y are connected, you have found a divisor > g of x and of y. You can record this and may be able to use it when you look for gcd(y, z). If g is large then using Euclid’s algorithm but stopping when you know that gcd(x, y) <= g might make things quicker. For example if g=100, and Euclid showed you ...


0

That's an interesting problem. First of all, calculating directly the gcd between two numbers is clearly the fastest way to decide if they are connected. But as you noticed, quite unefficient for your problem. A solution is to use prime factorization. Let's denote $P(z)$ the multiset prime factorization of a number $z$. Thus, you note that $gcd(x, y) = P(x) \...


0

$O(n)$, since you still will go through the entire array. And yes, this is a linear search since $O(n)$ is linear.


18

This problem (more formally its decision version) is NP-complete. NP-hardness can be shown via a reduction from the Job-Shop Scheduling Problem (JSP) with makespan objective, which is well-known to be NP hard. In the JSP, we have $n$ jobs $J_1, J_2, ..., J_n$. Within each job there is a set of operations $O_1, O_2, ..., O_n$ which need to be processed in a ...


0

The series $\frac{1}{2^k}$ is a geometric progression. Hence, $\sum_{k=0}^m \frac{1}{2^k} = \frac{1-\left(\frac{1}{2}\right)^m}{1-\left(\frac{1}{2}\right)}$ You can continue from here.


6

Thanks to "user2357112 supports Monica" for pointing out issues! Now fixed. Let's formulate the decision problem form of this problem, which I'll call Tree Scheduling (TS): Given a number $k$, and a rooted tree with tasks $t_1, \dots, t_n$ for vertices, each having some integer duration $l_i$ and requiring some resource $r_i$ from a set $S$ of ...


14

What you are describing is a planning and scheduling problem. Kautz and Selman pioneered the use of Boolean satisfiability and SAT solvers to attack such problems in the early 1990's. SATPLAN, STRIPS, and PDDL are good search terms for further research. There seem to be several planner implementations that take world descriptions written in STRIPS and ...


1

Your algorithm doesn't work. BFS doesn't explore all paths. One of the paths you haven't explored might have much higher strength than all the ones you have explored. There exists a counterexample with only four or five nodes (depending on the exact details of how you implement the steps outlined in your overview). I'll let you have the fun of finding it....


1

Suppose that you have a graph and each vertex is colored with one of three colors, and let the set of different-colored vertices be $A, B, C$. Now, try to find a triangle with one vertex from each partition. For each vertex $a \in A$, try let $B_a$ and $C_a$ be $a$'s neighborhood in $B$ and $C$, respectively. Now you only need to check if there is an edge ...


1

I think you've already done most of the work. Now it's just solving the recurrences $$T(n)=T(\frac{n}{2})+O(n)$$ and $$T(n)=T(\frac{n}{2})+O(n^2)$$ Both are pretty straightforward. The key is to keep substituting until you find a pattern, after which you analyze what will happen when the recursion bottoms out. There are 2 common methods, namely the recursion ...


1

Try to find an explicit formula for $T(n)$: Start by writing a few examples, such as $T(2)$, $T(4)$, etc. Then, after you got some intuition on how $T(n)$ behaves, formulate it as a summation, and find a closed form for it. I will give the example of how to do it for the "best case" scenario: Examples $T(2) = T(1) + c_1 \cdot 2$ $T(4) = T(2) + c_1 \...


1

Assume the array elements are in random order. Create a sorted array of size log n. Insert the first log n items. Then insert the next elements if they are larger than the smallest element in that array. Estimate how often the k-th element of a random array is within the (log n) largest elements so far, and how much work is done in that case. You’ll find the ...


2

The second loop in your solution requires time $O(\log n)$ and can be safely ignored since its time complexity is dominated by the previous sorting step. The call to Quicksort requires time $O(n \log n)$ in expectation and $O(n^2)$ in the worst case. You can solve your problem in $O(n)$ worst-case time as follows: create a max-heap with the elements in the ...


2

If I correclty understand the algorithm, your TM starts "marking" the first $a$, then it finds the first $b$ and marks it, then it comes back the the first unmarked $a$ and so on. So, assuming that you have in input a string $w$ of lenght $n$ that belongs to the language $L$, you have $\frac{n}{2}$ $a$'s that have to match with the same number of $...


3

The binomial, negative binomial, and hypergeometric distributions are discrete distributions. Knuth and Yao (1976) gave complexity results for discrete distributions in general. Given a stream of i.i.d. unbiased random bits, any algorithm that samples from a discrete distribution will require at least—$$b = -\sum_{x\in\Omega} \mathbb{P}(X=x)*\log_2(\mathbb{P}...


1

With regards to (3), there's a fairly simple algorithm to compute large exponents. exp(a, b) = if b is even let half = exp(a , b/2) return half * half else return a * exp(a, b-1) This will be logarithmic in the magnitude of $b$, meaning the number of multiplications is linear in the number of bits used to represent $b$. It's also a very ...


1

What would you think about a proof that says the following? $NP \subset DTIME(2^n)$ let $m = \log n$, then $DTIME(2^n) = DTIME(m) \subset P$ Therefore $P = NP$ Here, you have indeed $DPSACE(log^2n)\subset PSPACE$ but the argument is weird. Also please note that Savitch's theorem already proves that $NPSPACE \subset PSPACE$, and you have the result you want,...


0

(expanding on my comment) Technically No You need to be very careful here, as there is a difference between algorithmic time complexity and runtime. In the case you have described, the runtime may be O(n) but the algorithm itself is O(n+m). This is because, without your external constraints, the algorithm's time complexity cannot be determined without ...


1

arr[] can be considered a partial order, and the groups you're looking for are then called antichains. So, you're looking for a decomposition into a minimum number of antichains of the partial order represented by arr[]. According to Mirsky's theorem, the smallest achievable number of antichains is equal to the length of the longest chain -- that is, the ...


0

I have looked up a little bit about Thorup's algorithm (see here), but it turns out that: For simplicity, we assume […] that the input and output size is $O(m)$ Here, $m$ is the number of edges $|E|$. This assumption in fact proves that a hypothesis for the proof is $|V| = O(|E|)$ (since $V$ is part of the input). That means that even Thorup's ...


1

To the extent of my knowledge, applying BFS on a graph (directed or undirected), starting from the "source" node and visiting only nodes that we can reach using the BFS (that is, we don't run BFS from every node if we didn't see that node already. Only one instance starting from the source node is enough), would require $O(E)$ time. It follows ...


0

As you have said, there are $2^n-1$ total "decrements". Notice that at the $k$'th decrement, you "waste" $O(n)$ time on the left side, plus $O(k)$ at the right side. Sum everything up, from $k=1$ up to $k=2^n-1$: $\sum_{k=1}^{2^n-1} n+k = n(2^n-1)+\sum_{k=1}^{2^n-1} k = n(2^n-1) + O(2^{2n})=O(2^{2n})$


Top 50 recent answers are included