Skip to main content
Share Your Experience: Take the 2024 Developer Survey

New answers tagged

1 vote

Is it known whether EXP is contained/not-contained in P/log?

EXP is not contained in P/log. This can be likely proved by direct diagonalization, extending the proof of $\let\R\mathsf\R{P\ne EXP}$ as in the time-hierarchy theorem, using the fact that there are ...
Emil Jeřábek's user avatar
2 votes

Usage of matrix multiplication for distance products

Nice idea! But no, that doesn't work, alas. The problem with your approach is that the numbers become enormous, which makes matrix multiplication slow. It is tempting to say that the running time of ...
D.W.'s user avatar
  • 161k
2 votes

Polynomial solutions, one less

Suppose $L = \{(G_x, Y) \mid Y$ is the maximum or minimum vertex cover of $G_x\}$. This satisfies your requirements. Now let for $G_{x_0}$, we discard $Y_a$ as the maximum vertex cover (which is all ...
codeR's user avatar
  • 1,042
1 vote
Accepted

Harder version of the k-partition problem

Short answer: It doesn't look like it. For your first example, hardness results for higher levels of the polynomial hierarchy, this problem is in NP for all $k$ (since a solution can be verified in ...
Highheath's user avatar
  • 1,073
5 votes
Accepted

Showing the language of all graphs that are both 4-colorable and not 3-colorable is coNP-hard

Let's flip this around using the fact that $L$ is $\text{NP}$-hard iff $\overline{L}$ is $\text{coNP}$-hard. You want to show that $$\text{3-Col} \cup \overline{\text{4-Col}} \text{ is NP-hard}.$$ To ...
Benjamin Kuykendall's user avatar
2 votes
Accepted

Does NSPACE($n^2$) $=$ DSPACE($n^4$)?

I believe this is unknown. There are a couple of barriers: First, it is unknown whether Savitch's theorem is optimal. Imagine we could improve the theorem to show $$\text{NSPACE}(f(n)) \subseteq \text{...
Benjamin Kuykendall's user avatar
1 vote

Why is my O(n^2 * 2^n) code faster than O(n * 2^n) and O(2^n) codes for the LeetCode "Beautiful Subsets" problem?

Big-O doesn’t take constant factors into account. Modern computers can do 64 bit operations at a time, that’s a factor n if n <= 64. And if the time is O(n 2^n) then I bet n <= 64. So one ...
gnasher729's user avatar
  • 30.4k
1 vote
Accepted

Why is my O(n^2 * 2^n) code faster than O(n * 2^n) and O(2^n) codes for the LeetCode "Beautiful Subsets" problem?

Turns out Leetcode tests are just weak. I could find test cases such that the O(n^2 * 2^n) solution takes ages compared to the other two (...
FluidMechanics Potential Flows's user avatar
1 vote

Optimal lookup complexity when requiring insertion complexity to be at most $\mathcal O(\log\log n)$?

After mulling this over for a long time, I've convinced myself that there is no optimal lookup complexity when insertion complexity is limited to $\mathcal O(\log\log n)$. I've written up my reasoning ...
Franklin Pezzuti Dyer's user avatar
0 votes

P vs NP problem (Student example)

To solve an instance of this problem, you need to either find one solution or prove that no solution exists. Let’s say you picked 10 items and between them they are connected to 301 other items. It is ...
gnasher729's user avatar
  • 30.4k
-4 votes

P vs NP problem (Student example)

The only way to make the question viable is 1. 1 kid not on the list to go to the housing. that's the only way to make it a question without all the information. my algorithm works for any amount ...
Lancelot Foreman's user avatar
6 votes
Accepted

If coNP ⊆ NP, does that mean coNP = NP?

Yes. Assume co-NP ⊆ NP. Take any NP problem. Its complement is co-NP, therefore NP by co-NP ⊆ NP, so the problem itself is co-NP, QED.
Jean Abou Samra's user avatar
1 vote

Concise definitions for different types of computational problems

A search problem is defined by a verifier $V: \Sigma^* \times \Sigma^* \to \{0,1\}$. Given $x$, the goal is to find $y$ such that $V(x,y)=1$. A counting problem is similar, but given $x$, the goal is ...
D.W.'s user avatar
  • 161k
3 votes
Accepted

Why do we use summations when computing time complexity?

I think you might be slightly confused about what the notation $$\sum_{i=1}^n$$ means. In particular, it doesn't actually mean anything. There needs to be something "inside" (to the right of)...
NaturalLogZ's user avatar
2 votes

Floating point operations in a zero padded Strassen multiplication

See, the idea is to choose the next power of $2$ for $n$ so that we have $\frac{N}{2} < n \le N$. Then, in an asymptotic sense, it does not matter whether you use $n$ or $N$. Here's why: The actual ...
codeR's user avatar
  • 1,042
3 votes
Accepted

Floating point operations in a zero padded Strassen multiplication

You wouldn’t pad to a power of two. First, for small matrix sizes you would just produce the fastest code you can, without using Strassen at all. Then you figure out for which n a 2n x 2n matrix is ...
gnasher729's user avatar
  • 30.4k
0 votes

Robust maximum weight forests with weights on edges

The problem may not be NP-hard! Let us look at the following facts: The maximum-spanning tree problem is polynomial-time solvable There are only $n\choose 3$ ways the deletion and addition of edges ...
codeR's user avatar
  • 1,042
2 votes

Can remainder mod 2 be efficiently computed from addition and equality?

I really like this question! Here's a sketchy argument for a negative answer (as expected) which I think works but may need some details filled in: Suppose our putative polytime parity-checking ...
Noah Schweber's user avatar
3 votes

How to Determining the Big O Complexity of a Recursive Function?

The definition you've given for the sequence $f(n)$ is $$f(n) = \begin{cases} 0, &n = 1 \\ f(n-1) + f(\lfloor n/2 \rfloor), &n \ge 2 \end{cases} $$ Note that you've given $f(1)=0$, not $f(0)=...
Ashwin Ganesan's user avatar
4 votes
Accepted

How to Determining the Big O Complexity of a Recursive Function?

None of the answers are correct, the recursive equation $$T(n) = 1 + T(n-1) + T(\lfloor n /2 \rfloor), \quad T(0) = 1$$ gives solution $T(n) = {}$$\text{A346912}$$(n) = 2 \cdot $$\text{A000123}$$(n) - ...
orlp's user avatar
  • 13.6k
4 votes
Accepted

Why is the number of array accesses not considered in analyzing the complexity of mergesort?

To make our lives simpler, we often focus on the dominant operation for analyzing the running time of an algorithm. This laziness usually does not hurt us since we are mostly concerned with asymptotic ...
codeR's user avatar
  • 1,042

Top 50 recent answers are included