# Questions tagged [computational-complexity]

Use for questions about the efficiency of a specific algorithm (the amount of resources, such as running time or memory, that it requires) or for questions about the efficiency of any algorithm solving a given problem.

3,287 questions
Filter by
Sorted by
Tagged with
12 views

33 views

### Reduction : 3-Dimensional Matching $\leq$ $_{p}$ subset sum Explanation

excuse me, could someone explain to me the reduction of the problem 3-dimensional matching to subset sum? I was reading Jon Kleinberg's design algorithms book and when I came across this reduction I ...
• 51
1 vote
46 views

### Partition a positive integer sequence into subsequencies of equal weight

For a finite sequence of $N$ positive integers $a_1, a_2,.., a_N$ let us define its weight as $w (\{a_i\}) = \log(N) \cdot \sum_{1}^{N}{a_i}$. I want to partition such sequence into $K$ non-empty ...
1 vote
27 views

### Finding solutions to Boolean satisfaction problems

How hard is it to find a solution to an instance of SAT if we know that the instance is satisfiable? Clearly, finding a solution to a SAT instance is at least as hard as deciding whether the instance ...
9 views

### The amortized complexity of visiting $m$ keys in order in B-tree with $N$ items

I read a paper that said the amortized complexity of visiting $m$ keys in ascending order in a $b$ tree with $N$ keys is $O(1 + \log(N/m))$. I am wondering why it is not $O(1 + (\log N)/m)$ because ...
436 views

• 101
19 views

### Is One Way TSP NP-complete?

I know that One Way TSP (TSP but the salesman does not have to return to his original city) is NP-Hard, but is it NP-Complete? I ask this because I recently found a solution to Open TSP but can't find ...
• 127
1 vote
45 views

### What is the complexity of global solution of a nonlinear system?

Consider an $n$-dimensional system $F_j(x_1, \ldots, x_n) = 0, j = 1, \ldots, n$. The functions $F_j$ can be considered as monotonic w.r.t. all $x_i$. What is the complexity of the problem of finding ...
• 248
30 views

### Notion of circuit width seems to have little to do with memory.

As suggested in the title, I'm unhappy with the notion of circuit width I've been given in my computational complexity class. It was motivated as a model of amount of memory needed for the algorithm, ...
• 409
1 vote
84 views

### Is there a general algorithm to decide whether an integer value is attainable by a quadratic form?

I'm not sure if I phrased the question correctly, but let's say that due to a result called 15 theorem that "if a positive definite quadratic form with integer matrix represents all positive ...
1 vote
12 views

• 1,697
### Why trial dividing r into n takes $O(\log(r)\log(n))$ operations
I'm very new to time complexity and i'm trying to understand this small part of a text i was given. I have list of primes, $r$, up to a number P. My text says that trial dividing these $r$'s into $n$ ...