the amount of time resources (number of atomic operations or machine steps) required to solve a problem or run an algorithm with respect to the input size.

learn more… | top users | synonyms

3
votes
1answer
87 views

Complexity of the decision version of determining a min-cut

I was wondering what the complexity of the following problem is: Given: A flow network $N$ with a source $s$, sink $t$ and a number $k$. Question: Is there an $s$-$t$ cut of capacity at most ...
-2
votes
0answers
20 views

Worst/Best cases [closed]

For the two functions, would their worst/best Big O cases change compared to each others? If so, how would they change. I believe that when dealing with Big O, order is the only thing that matters, so ...
-1
votes
0answers
27 views

Big O notation for Python [closed]

I am unsure of the order of growth for these two procedures in Python. Can someone please explain: def modten(n): return n%10 and ...
2
votes
0answers
24 views

Complexity of Sorting Integers on a Multitape Turing Machine

How expensive is sorting integers on a Multitape Turing Machine? The usual algorithms rely on indirect access, so how much does losing it cost us? Say we have $N$ integers from $[0, 2^B)$. It's not ...
7
votes
2answers
95 views

Why is the transform in Schönhage–Strassen's multiplication algorithm cheap?

The Schönhage–Strassen multiplication algorithm works by turning multiplications of size $N$ into many multiplications of size $lg(N)$ with a number-theoretic transform, and recursing. At least I ...
3
votes
2answers
72 views

Find rectangle of minimum area where dimensions are larger than minimum

Problem: Given a collection $S$ containing $|S|=n$ rectangles defined by dimensions $(x,y)\in R^2$ (width and height of rectangles are real numbers), find the rectangles with the minimum area ($A_i = ...
7
votes
1answer
644 views

Why doesn't Knuth's linear-time multiplication algorithm “count”?

The wikipedia page on multiplication algorithms mentions an interesting one by Donald Knuth. Basically, it involves combining fourier-transform multiplication with a precomputed table of ...
1
vote
1answer
36 views

What is the time complexity of the Bailey–Borwein–Plouffe formula?

How can I assess and derive the time complexity of the BBP formula? $$ BBP(n)=4S(1,n) - 2S(4,n) - S(5,n) - S(6,n) $$ where $$ S(j,n) = ...
3
votes
1answer
59 views

Computing the complement of a set

Suppose I have a set $A$ of elements in $\{1, \ldots, n\}$, given as an unordered list. I would like to compute the complement of $A$, i.e., I would like to produce an unordered list of entries in ...
2
votes
1answer
65 views

Is FNP = FEXPTIME if and only if NP = EXPTIME?

It is very well known that if the classes $\sf FP$ and $\sf FNP$ are equal, then also the classes $\sf P$ and $\sf NP$ are equal (see e.g. FNP on Wikipedia). Is it also true that if $\sf ...
-3
votes
1answer
56 views

exponential lower bound on boolean formula conjunctions, what complexity class? [closed]

this new paper A Lower Bound for Boolean Satisfiability on Turing Machines by Hsieh asserts an exponential lower bound for a TM time complexity on a problem of finding whether a solution exists to a ...
5
votes
1answer
61 views

Computing the number of bits of a large power of integer

Given two integers $x$ and $n$ in binary representation, what is the complexity of computing the bit-size of $x^n$? One way to do so is to compute $1+\lfloor \log_2(x^n)\rfloor=1+\lfloor ...
3
votes
3answers
80 views

Minimum number of tests to identify subset of modules that trigger a bug?

I have an ordered set of $M$ software modules compiled together. The interaction of some $N$-tuple of these modules is causing a bug when the program is run. I can run the program with any desired ...
1
vote
2answers
72 views

Is the Calibron 12 puzzle NP-hard?

So, I was analyzing the Calibron 12 puzzle and to me it looks like a bin-packing problem. Is this puzzle actually a bin-packing problem and thus NP-hard for the perfect solution? Basically, you can ...
2
votes
0answers
37 views

Non-deterministic time hierarchy theorem: universal TM overhead

I am currently reading the book of Arora and Barak on computational complexity. In the third chapter (p69-70), two classic theorems regarding time complexity hierarchies are introduced: ...
2
votes
2answers
54 views

Why do Computers use Hex Number System at assembly language?

Why do computer use Hex Number System at assembly language? Why don't they use any other number system like binary, octal, decimal? What thing forced computer designer to use hex system at assembly? ...
-1
votes
1answer
54 views

A difficult master theorem problem

Consider the function $B:\mathbb{N}\rightarrow\mathbb{R}$ defined by $$ B(n) = \begin{cases} 1 &\text{if $n\le 2$}\\ B\left(\left\lceil\frac{n}{\log_2n}\right\rceil ...
-1
votes
1answer
39 views

Is P^SAT subset of sum of NP and co-NP

I have a following problem: Let $P^{SAT}$ be a class of problems decidable by a deterministic polynomial Turing Machines with SAT oracle. (only one question to oracle). Assume that: $co-NP \neq NP ...
1
vote
1answer
39 views

Can weighted problem have polynomial complexity if non-weighted problem is NP-complete: hitting set

I am confronted with task to find polynomial time complexity solution for weighted hitting set problem. I have found that usual hitting set problem is NP-complete and therefore the task seems to be ...
3
votes
1answer
48 views

Finding minimum path in a matrix algoritm

I'm looking for an algorithm that do the following thing. Given $n$ the number of rows and columns of a matrix of positive integers. Given $(x_1,y_1)$ the starting coordinates. Given $(x_2,y_2)$ ...
-3
votes
1answer
53 views

Compare runtime for algorithms?

I try to compute the asymptotic runtime for this algorithm and compare it with other algorithm $A = (C -(D * E ) ) mod p$ $ B = ((C * (D)^{-1} - (E * F ))$ mod p if we suppose each value A, B, C, D, ...
1
vote
1answer
82 views

Nested loops: Still $\mathcal O(n)$?

I have an algorithm similar to this: i=1 while(i < n) { //something in O(1) while(i < n && cond) { //something in O(1) i++ } i++ } ...
0
votes
1answer
43 views

Time complexity of Dynamic Array via repeated doubling

When we implement dynamic array via repeated doubling (if the current array is full) we simply create a new array that is double the current array size and copy the previous elements and then add the ...
1
vote
1answer
101 views

Analysis of a recursive algorithm, where running time strongly depends on input

I want to find the worst-case running time of an algorithm, which follows the following recurrence equation: The worst-case running time is $\Theta(n^2) + T(n, 2, n)$, where $T(x, i, y) = ...
0
votes
0answers
69 views

Recurrence Equation in Algorithm [duplicate]

Can anyone help me in solving this complex recurrence? \begin{eqnarray} T(n) &=& n +\sum_{k-1}^n T(n-k)+T(k) & Where& T(1) = 1. \end{eqnarray} although this topic will already ...
0
votes
0answers
22 views

Using arithmetic progression sum to show an algorithm is both $\Theta(n^2)$ and $O(n^2)$ [duplicate]

Exercise 4 in http://discrete.gr/complexity/ askes to give an arithmetic progression sum to show that the following algorithm is both $O(n^2)$ and $\Theta(n^2)$. ...
2
votes
1answer
78 views

Sorting numbers in $O(1)$

Here is an experiment I came up with (I don't have sufficient material to make it): Say that, you have a list of $n$ numbers $L = \{l_1, l_2, ..., l_n\}$. And you have bars representing those numbers ...
-1
votes
1answer
56 views

CNF H is in the class P

CNF H = {<ø>|ø is a satisfiable cnf-formula where each clause contains any number of literals, but at most one negated literal} I want to show that CNF H ...
3
votes
1answer
52 views

big O of a complex function

I have a complex function, which looks something like this: $$f(x) = \sum_{k=0}^x{\frac{g(k)}{h(k)}} + l(x)$$ Now, $g(k) = O(\log k)$ and $h(k) = O(k)$, the sum iterates $k$ from $0$ to the ...
2
votes
1answer
31 views

Understanding Expected Running Time of Randomized Algorithms

I want to understand the expected running time and the worse-case expected running time. I got confused when I saw this figure (source), where $I$ is the input and $S$ is the sequence of random ...
0
votes
0answers
18 views

TFNP and #P relation

Is there any known relationship between the complexity classes TFNP and #P. On first sight, it seems we can not compare them. Is there any work done either about this question, or about something ...
0
votes
0answers
26 views

The time complexity to find the largest rising left-neighbourhood for every element in an sequence? [duplicate]

For example, in sequence 3, 4, 3, 2, 4, the largest rising left-neighbourhood for 2 is 4 3 2 ...
1
vote
0answers
26 views

General object recognition versus specific object recognition

I have a question about the difference between general object detectors and specific object detectors. By specific object detectors, I'm referring to classifiers/object recognizers that are built to ...
1
vote
0answers
19 views

Grover algorithm for known number of solutions

I am reading Computational Complexity book and specifically Grovers search algorithm. I am aware that if we knew in advance exact number of solutions $K$, then the basic algorithm can be tweaked to ...
4
votes
1answer
117 views

Complexity of bitwise AND operation on bit string regular expressions

Given two regular expressions of bit strings $B_1$ and $B_2$ of the same length (stated mathematically, $B_1,B_2 \in \{0,1\}^m$) that use only grouping and repetition, what is the optimal running time ...
4
votes
1answer
68 views

Relation between RAM and Turing machine

Denote $D$ a set of finite sequences of integers. In Papadimitriou's "Computational Complexity" in theorem 2.5 it is proved that if a RAM program $\Pi$ computes a function $\phi$ from $D$ to integers ...
3
votes
1answer
55 views

Complexity of factoring products of distinct prime numbers

Problem: Input is an integer number $x$ that we know factors as $p_{i_1}\cdot p_{i_2}\ldots p_{i_n}$, where the $p_{i_j}$'s are distinct prime numbers. Output is the above factorization of $x$. Do ...
1
vote
1answer
98 views

Inclusion of complexity classes (Deterministic Turing Machine)

I can't understand what my professor wrote about these inclusions concerning deterministic classes: $$ DTIME(f) \subseteq DSPACE(f) \subseteq \sum_{c\in\Bbb N}DTIME(2^{c(log+f)}) $$ I understood ...
4
votes
1answer
57 views

$NP\subseteq TIME[O(n^{\log n})]$

Is it more plausible that $NP\subseteq TIME[O(n^{\log n})]$ than $NP\subseteq P$? I don't see this mentioned much and is there a reason why? If this question doesn't make sense, explain why.
2
votes
1answer
28 views

Efficient lookup when key is made of multiple elements and elements can be empty

I am wanting to create a map where the key contains multiple elements and the elements can be empty/null. The empty values are treated as "anything". I want to lookup function to match when the stored ...
3
votes
2answers
81 views

Count number of ways to place ones in an $M \times M$ matrix so that every row and column has $k$ ones?

On math.stackexchange, someone asked how to count the number of ways to place $1$'s into a $10 \times 10$ matrix so that every row and column has $5$ $1$'s. Each element of the matrix must be either ...
3
votes
2answers
126 views

Has there been any more progress on P vs. PSPACE compared to P vs. NP?

I understand this is a slightly vague question, but there are results for P vs. NP, such as the question cannot be easily resolved using oracles. Are there any results like this which have been shown ...
2
votes
1answer
111 views

Why is TIME(n log (log n)) \ TIME(n) = ∅?

In my computation book by Sipser, he says that since every language that can be decided in time $o(n \log n)$ is regular, then that can be used to show $TIME(n \log (\log n))\setminus TIME(n)$ must be ...
3
votes
2answers
292 views

How to determine if a black-box is polynomial or exponential

I have a problem which essentially reduces to this: You have a black-box function that accepts inputs of length $n$. You can measure the amount of time the function takes to return the answer, but ...
2
votes
2answers
65 views

Is summing over all possible $k$-combinations NP-hard?

Say we have a set of numbers $A=\{a_1, a_2, \dots, a_n\}$, and we wish to sum over all possible combinations of $k$ terms to compute $$ \sum_{\substack{C \subseteq \{1,2,\dots,n\} \\ |C|=k}} \prod_{c ...
8
votes
1answer
101 views

Maximum Stacking Height Problem

Has the following problem been studied before? If yes, what approaches/algorithms were developed to solve it? Problem ("Maximum Stacking Height Problem") Given $n$ polygons, find their ...
2
votes
1answer
27 views

Complexity as it relates to verifiers of languages

So I've been thinking about verifiers and a possible relation between a language's class and it's verifier complexity. From the book, "NP is the class of languages that have polynomial time ...
2
votes
0answers
28 views

Lower-bounds of running-time for output sensitive Algorithms

Let me ask my general question using a specific example, namely range searching: Given a set of points in the plane and an axis parallel rectangle, report all points lying in the rectangle. If the ...
4
votes
2answers
186 views

Performance impact due to time required for shuffling in Quicksort

As a programmer with non CS background, I am learning algorithms. When explaining the performance of quicksort in an Algorithm book and also elsewhere on the web, I do not see any reference to the ...
2
votes
1answer
27 views

Polynomial hierarchy intersection

While familiarizing myself with polynomial hierarchy, I have come across a problem of showing $NP^{\Sigma_{k}^{p} \cap \Pi_{k}^{p}} \subseteq \Sigma_{k}^{p}$. By looking at the proof for $NP^{SAT} ...