Computational complexity, a part of theoretical computer science that deals with understanding how efficiently a problem can be solved.

learn more… | top users | synonyms (1)

0
votes
2answers
65 views

Complexity class P - is $k$ only natural numbers?

I think I have seen an algorithm that has $x^{1.5}$ as its complexity. However, according to Wikipedia, it states that the complexity class P is defined as $\bigcup_{k\in\mathbb{N}} ...
0
votes
1answer
327 views

symmetric difference of languages - both are in NP and coNP

I have this problem, Let $L_1,L_2$ be languages in $NP \cap co-NP$. I want to show that their symmetric difference is also in $NP \cap co-NP$. Like: $L_1 \oplus L_2 = \{x | x$ is in exactly one of ...
3
votes
2answers
118 views

Is it possible to prove that a problem $P$ is decidable in $O(\phi)$ without providing an algorithm that decides $P$ in $O(\phi)$?

Phrased another way: Are there any problems that are known to be decidable in a better worst-case time complexity than the best known procedure?
2
votes
2answers
354 views

the set of sentences (i.e. closed formulas) of first-order logic and the Chomsky hierarchy

The set of well-formed formulas (wffs) in first-order logic (FOL) is decidable, because it's straightforward to translate the standard recursive syntax rules into a context free grammar, and all ...
0
votes
1answer
247 views

Time complexity of algorithm computing averages

I am new, and wanted to see if someone can help me. What is the running time of your algorithm (below) with respect to the variable $n$? Give an upper bound of the form ${\cal O}(f(n))$ and a ...
0
votes
1answer
873 views

What is the computational complexity of a brute force perfect numbers finder algorithm?

A loop goes thru all numbers from one to N to find perfect numbers. For each number in the range, it checks all numbers less than it to see if it's a divisor by modding it by the number and checking ...
2
votes
2answers
279 views

Knapsack with non-trivial “utility” function

The standard knapsack problem imagines a thief trying to stick the most items in his knapsack as possible. It assumes that having, say, two Picasso paintings is twice as good as having one. We might ...
2
votes
0answers
221 views

2-Player Game PSpace-Completeness

So there is a n x n game board and each location on the board has an integer. Player one picks a number from row 1 and player 2 picks a number from row 2 and they alternate until there are no more ...
0
votes
1answer
545 views

NP-Completeness of Certain Bounded Degree Graphs

I was studying time complexity when it comes to bounded degree graph problems and I was wondering if I can get help with the following two problems. 1) L = set of all (G, k) where G is a graph with ...
1
vote
2answers
696 views

P or NP-Complete? (concerning 2-CNF formulas)

I have two languages that I want to either prove is in P or NP-complete. 1) 2-CNF formulas where there exists an assignment that satisfies the 3/4 of the first 1000 clauses and all of the rest. 2) ...
0
votes
1answer
78 views

How do I estimate the time taken? (Growth Rates)

Suppose you have a program that solves an AI problem. When the problem size is $N = 1,000$ your program takes 10 seconds to find a solution. Estimate the time it will take to solve a problem of size ...
4
votes
1answer
158 views

Connect 4 - SAT

My question is about how the Hasbro game Connect4 can be viewed as a SAT problem. My initial guess is that it would actually be QSAT, and that the 'problem' would be something along the lines of: "Is ...
8
votes
1answer
3k views

Complexity of counting the number of triangles of a graph

The trivial approach of counting the number of triangles in a simple graph $G$ of order $n$ is to check for every triple $(x,y,z) \in {V(G)\choose 3}$ if $x,y,z$ forms a triangle. This procedure ...
3
votes
1answer
279 views

Proving NP-completeness intuition

When approaching a problem in NP, initially not knowing whether the problem is in P or NP-complete (or some other choice). It seems to me the only way one can go about "solving" this problem is to ...
4
votes
0answers
206 views

Proving NP-completeness (hardness) exercises

I am looking for a list of exercises that can be done to practice polynomial time reductions to prove NP-hardness of problems. I know there are hundreds (thousands?) of problems proven to be NP-hard. ...
3
votes
1answer
103 views

Treatments of Mahaney's Theorem?

Could you direct me to some readable treatments of Mahaney's theorem? The best thing I've been able to find is Fortnow's lecture. I'm especially interested in discussion around the theorem and its ...
4
votes
2answers
1k views

what is the computational complexity of solving a quadratic program with linear inequality constraints

I'm aware of several solution methods and have several solvers at my disposal, but I can't for the life of me find analysis on the complexity. In particular, I'm interested in the complexity of ...
4
votes
1answer
240 views

if P=NP, then is E=NE?

If the computational complexity class P equals to NP, does the complexity class E equal to the class NE? E is defined as $DTIME(O(2^{O(n)}))$ NE is defined as $NTIME(O(2^{O(n)}))$ Thank you very ...
6
votes
0answers
579 views

The Average Running Time Of Euclid Algorithm?

What is the average running time of Euclid Algorithm with respect to all possible input pairs $(m,n)$ such that $\gcd(m,n) = d$? It seems very hard to deduce from the recurrence $T(m,n) = T(n, m ...
2
votes
1answer
355 views

what is the relationship between the complexity class E(and EXP) and NP?

I want to know any relationship between the complexity class E(and EXP) and NP. I also would like to know whether there is any $DTIME$ formulation or relations of $NTIME(O(n^k))$ where n is the size ...
0
votes
1answer
587 views

What's the big $O$ for this summation?

What would the big $O$ (worst-case runtime complexity; I think it's big $O$?) be for an algorithm that takes this long? I generalized the run time with the summation and put it in wolfram alpha. ...
10
votes
2answers
826 views

How hard is it to do arithmetic?

People in computing are often observed saying that a computation takes $\operatorname{O}(n^3\log n)$ steps or that it's NP-hard or that it's not computable, or that it's primitive recursive, etc. I ...
2
votes
0answers
267 views

Complexity of finding solutions for a system of polynomial equations

Problem A: Given a set of polynomial equations $ f_1=0,\ldots,f_m=0 $, where the $ f_i $'s are multivariate polynomials with $ n $ variables over a field $\mathbb F$, decide whether there is a ...
6
votes
2answers
725 views

Optimization Puzzle

You are given a large number of LEGO blocks of size 1. You can build blocks of other sizes using smaller blocks. For example, you can build a block of size 2 using two of size 1 blocks and then build ...
2
votes
0answers
73 views

On bounding the average cost of top-down merge sort

Let $A_n$ be the average number of comparisons to sort $n$ keys by merging them in a top-down fashion (see any algorithm textbook). It can he shown that $$ A_0 = A_1 = 0;\quad A_n = ...
5
votes
2answers
998 views

Why is integer factorization considered to be in NP if a quantum computer can compute a factorization in polynomial time?

Sorry if this seems off topic, the cstheory guys told me it was off topic over there, and sent me here. Shor's algorithm on a quantum computer can solve an integer factorization problem in polynomial ...
0
votes
1answer
129 views

Determining computational complexity of stochastic processes

I have an program which implements a Markov chain Monte Carlo process on a system of N bits, stopping when the process converges. Let's use T to denote the average number of steps made by the Markov ...
5
votes
1answer
469 views

how can i prove that square root of n is space constructible

I know that square-root of n is space-constructible. I can't prove it by the space-constructible definition. How can I show that only $\sqrt{n}$ space is used?
3
votes
0answers
201 views

Amortized Analysis for (2,5)-Tree

I need some help with the following problem Definition: A (2,5)-tree is an external search tree, where all leaves have the same depth. Each inner node in a (2,5)-tree has at least 2, and at most 5 ...
5
votes
2answers
347 views

Precision and performance of Euclidean distance

The usual formula for euclidean distance that everybody uses is $$d(x,y):=\sqrt{\sum (x_i - y_i)^2}$$ Now as far as I know, the sum-of-squares usually come with some problems wrt. numerical ...
2
votes
1answer
786 views

Turing Machine Vs Linear Bounded Automata

Example of language accepted by Turing Machine but not by Linear Bounded Automata ? Is there any EXPSPACE language?
6
votes
1answer
146 views

What is wrong with this decision procedure for 3SAT?

So I came up with a decision procedure for 3SAT which would seem to be completeable in a polynomial amount of time. Naturally, I am assuming it is incorrect, but I don't know where the mistake is. ...
1
vote
0answers
785 views

Amortized analysis using potential function [Exercise from *Introduction to Algorithms*]

I need some help with the following problem from Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein: Consider an ordinary binary min-heap data structure with $n$ elements that supports ...
70
votes
4answers
2k views

Complexity class of comparison of power towers

Consider the following decision problem: given two lists of positive integers $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_m$ the task is to decide if $a_1^{a_2^{\cdot^{\cdot^{\cdot^{a_n}}}}} < ...
3
votes
2answers
428 views

Asymptotically optimal algorithms

Suppose one has an algorithm to solve a problem using at most f(n) computations with size of input n. How to prove, if such is the case, that this algorithm is the fastest possible for solving this ...
5
votes
1answer
140 views

Minimal DFA satisfying a finite view of a language.

Say one has a language $L \subseteq \Sigma^*$, but one doesn't know what strings are actually part of the language. All one has is a finite view of the language: a finite set of strings $A \subseteq ...
1
vote
1answer
117 views

Polynomial-time reduction

How can I prove it? $A \le_p B \Leftrightarrow \overline{A} \le_p \overline{B}$. $A \in \mathcal P \Leftrightarrow \overline{A} \in \mathcal P$. $\overline{A} = \Sigma^* \setminus A$
1
vote
1answer
85 views

Finding a subsequence (of a very long sequence) which does not sum to an even number

[Edited. I've revised to problem to focus on the special case of the integers modulo 2.] You are given a function f from binary strings x ∈ {0,1}n to the integers, or (without loss of ...
0
votes
1answer
268 views

NLogSpace and CoNLogSpace

Assume S1, S2∈ NLOGSPACE. Which of the following statements is true? • S1 \ S2 ∈ coNLOGSPACE • S1 Δ S2 ∈ NLOGSPACE where A\B is the set of members of A that are not members of B. And A Δ B is the set ...
4
votes
1answer
233 views

H-minor free Graph

Recently I cam across a statement which divides graphs into different classes w.r.t. the complexity of problems on them. planar < bounded genus < H-minor free < general graphs My question ...
5
votes
3answers
8k views

Worst case complexity of the quicksort algorithm

Good evening, I have a doubt concerning the worst case scenario of the quicksort algorithm, based on the number of comparisons made by the algorithm, for a given number of elements. This is part of ...
1
vote
2answers
226 views

Is Turing completeness monotone with respect to Cook reductions?

I think the post title is relatively clear assuming I worded it correctly, but since I was thinking of a specific example: The language of Boolean expressions is Turing complete; Does this imply that ...
3
votes
1answer
175 views

Making sense of the various definitions of computational complexity

I'm a math student and have encountered the concept of computational complexity in several subjects in the course of my studies (numerical analysis, cryptography, intro to computer science and ...
1
vote
1answer
261 views

Complexity of a recursive function

I have a recursive function, and I'm trying to figure out it's complexity. denote P(n) - the runtime of the function (when given the parameter n). I know that : P(n)=n+(n-1)*P(n-1) [p(1)=1] How can I ...
4
votes
1answer
234 views

complexity theory: consequences of P vs NP

I have a basic question regarding the ramifications of P vs NP. If P=NP, then SAT would be in P. If I understand the definitions correctly, this would imply that there is a Turing machine which ...
4
votes
1answer
111 views

How to show that the complexity of a function is $O(\text{polynomial})$

Let $A=\{1,2,4,8,16,32,...,2^k,...\}$, and let $f:A\to \mathbb{N}$ be defined by : $$f(n)=\binom{n}{\log n}=\frac{n!}{(\log n)!*(n-\log n)!}$$ I would like to find out if there exist a polynomial ...
2
votes
1answer
5k views

An algorithm for arbitrage in currency exchange

I found a really interesting problem and I wanted to hear people's opinion. It has to do with currency exchange rate. If we are give some coins $c_1,c_2,\dots,c_n$ and an array $R$ that keeps the ...
10
votes
1answer
340 views

Algorithm for a deck manipulation

Let's say you have a randomised deck of $N$ different cards. An $M$-action ($M\le N$) is defined as follows: you look at the top $M$ cards of the deck, put as many of them as you choose on top of the ...
4
votes
1answer
158 views

Vertex arrangement on the unit sphere

The problem is how can I solve a following in polynomial time? There is a graph $G$ with $n$ vertices, and the goal is to find an arrangement of its vertices on an $n$-dimensional unit-sphere so as to ...
5
votes
1answer
180 views

Primality Testing in $\mathcal{O}_{\mathbb{Q}(\sqrt{d})}$?

What is known about the computational complexity of primality testing in $\mathcal{O}_{\mathbb{Q}(\sqrt{d})}$ where $d$ is a square-free number? For what values of $d$ is primality testing easy ...