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
0answers
117 views

Verifying Algebraic Formulas

Say you are given an arbitrary Algebraic Formula: $$G(u_1,u_2,u_3...u_n) = 0$$ Where the expression $G$ is allowed to utilize: $+, - , *, /$ however desired $()$ however desired The operator $P(...
3
votes
1answer
363 views

Bound on total divisions of Euclid's Algorithm.

Question Suppose $\lambda$ is a positive integer and I want to show that there exists integers $a,b$ such that $a > b > 0$, $\lambda \geq \log_2b/\log_2\phi$, and Euclid's Algorithm on $a,b$ ...
2
votes
1answer
120 views

Will a problem be polynomial time solvable if a mathematician gives a procedure?

For a decision problem, if a mathematician finds a simple polynomial time procedure that solves it, does it mean that the problem is polynomial time solvable? For example, consider a decision problem:...
2
votes
0answers
49 views

Abelian SubGroup Variant:

Consider the following problem: Find integers $x_1, x_2, x_3,\dots, x_n$ Such that: $$P(x_1,x_2,\dots, x_n) = Q$$ for some integer $Q$ and polynomial $P$ where for all permutations of any set of ...
4
votes
1answer
5k views

Upper bound for $T(n) = T(n - 1) + T(n/2) + n$ with recursion-tree [duplicate]

I'm reading through Introduction to Algorithms, 3rd ed. and I got stuck on the following recurrence (exercise 4.4-5): $$T(n) = T(n - 1) + T(n/2) + n$$ The exercise asks you to find the upper bound ...
2
votes
1answer
47 views

Differentiating between prime/semi-prime and other integers

Does there exist a test that checks if a number is prime or a semi prime in polynomial time? I am aware that AKS can be used to check primality but what about semi primality? ========================...
1
vote
0answers
76 views

Quadratic Diophantine Primality Testing

Define a 2-Quadratic Group Operation as the following: A 2nd degree polynomial of the form: $$a_1x_1 + a_2x_2 + a_3x_1^2 + a_4x_2^2 + a_5x_1x_2 $$ Define a primal 2-quadratic group number as an ...
3
votes
5answers
745 views

Provide an algorithm $O (n ^ 3 \log n)$, any example?

Provide an algorithm computing performance $O (n^3 \log n)$. Your algorithm should contain only simple operations. Any idea of how to approach this problem?...I am studying for the computer science ...
2
votes
2answers
126 views

Computation of the mean of a random variable to estimate algorithm complexity

I made an incremental algorithm which I would like to evaluate the complexity. The algorithm works with a sliding window of size n. To study the complexity, the window is considered full and the data ...
2
votes
1answer
152 views

Finding the shortest/“most negative” closed directed trail in a weighted digraph with negative weights

I'm using the following definition of a "closed directed trail": a closed directed trail is a directed cycle in a digraph where all edges are distinct. Note that vertices may be repeated, so long as ...
2
votes
2answers
231 views

Find the smallest natural number not in a given set of integers

What is the computational complexity of this task? The goal is to compute the number $x=\min(\Bbb N\setminus A)$, where $A$ is the input list and the complexity parameter is $n=|A|$ (which is finite). ...
1
vote
0answers
84 views

Systematic way of creating the complement of a regular grammar?

Regular languages are closed under complement. And any regular language can be generated using a regular grammar. Is there a systematic way to create the rewrite rules for the complement of a regular ...
9
votes
5answers
567 views

A computer's memory is finite, so how can there be languages more powerful than regular?

A computer has a finite memory. There are no computers with infinite memory. Therefore the only languages that a computer can process are those whose member strings are finite. As I recall, the ...
3
votes
1answer
134 views

Why do complex grammars require powerful algorithms?

I am reading a fabulous book on Formal Languages and in the book it says: As the rewrite rules of a grammar become more complex, the algorithm for recognizing the associated language becomes ...
2
votes
1answer
26 views

Complexity of finding fixedpoint

Suppose I have a fixed $n$-dimensional vector space $V$ over a field $F$ and I have a sequence of $n'$-linear transformations $G_i:V\rightarrow V$, $i \leq n'$. Further suppose I know that there is a (...
0
votes
2answers
167 views

Is polynomial time reduction commutative?

True or False: $D_1$ and $D_2$ are decision problems, and $D_1 \leq_p D_2$, then cannot be that $D_2 \leq_p D_1$ I think it is false because we already have a mapping for all yes instance from $D_1$ ...
2
votes
0answers
131 views

Solving a particular system of Diophantine equations in $n$ variables (Frobenius equations)

I have a particular system of linear Diophantine equations in $n$ variables for which I need to find all nonnegative integer solutions. Specifically, they are Frobenius equations, meaning the ...
0
votes
1answer
90 views

Cyclic Groups: Modulo operations in exponents possible?

I'm trying to follow CCat's Zero Knowledge Proof example, which was quite similar to the $\Sigma$-protocol example in my books. And whith both of them I'm struggeling. When I try to test CCats Example:...
2
votes
2answers
567 views

Solving Summation Expressions

I would like to know how do you solve summation expressions in an easy way (from my understanding). I am computer science student analyzing for loops and finding it's time complexity. e.g Code: <...
1
vote
0answers
74 views

Fixed Length Cycle Search

I am given a list of $0 \le M \le 2n(n-1) $ edges of a graph. My goal is to find a connected subgraph of this graph such that the degree of every vertex in the subgraph is $n$ that has exactly $n$ ...
0
votes
1answer
385 views

Solving a recurrence relation with floors and comparing it with other complexity classes

The problem that I am struggling with is the recurrance relation $T(n) = \lfloor(T(n/2))\rfloor + \lfloor(log \space n)\rfloor$ Where $T(1) = 1$ I am supposed to answer true/false to each of the ...
3
votes
1answer
261 views

Using the definition of big-oh notation, show that for any $k,\gamma>1$, $n^k=O(\gamma^n)$.

This question had been on my midterm in a course I took last year: Prove that for any $k,\gamma>1$, $n^k=O(\gamma^n)$. Intuitively, this makes sense. Even the fastest exponential algorithm (...
1
vote
0answers
42 views

Polytime programming

Given a linear system of the form: $$x_r = a$$ $$x_j = b$$ $$c_1x_1 + c_2x_2 ... c_nx_n = n$$ $$x_1 + x_2 + x_3 ... x_n = k $$ $$0 \leq a,b,x_1, x_2, x_3 ... x_n \leq 1$$ $$k \geq 0$$ How quickly ...
4
votes
4answers
543 views

Computing partition numbers

Today a friend and myself came up with the question of computing partitions of numbers, i.e.: given a number $n$, what is the number $p(n)$ of was of different ways writing $n$ as a sum of non-zero ...
7
votes
1answer
149 views

complexity of matrix multiplication

For $n\times n$ dimensional matrices, it is known that calculating $\operatorname{tr}\{AB\}$ needs $n^2$ scalar multiplications. How many scalar multiplications are needed to calculate $\operatorname{...
2
votes
1answer
173 views

Why is it so difficult to prove that the discrete Fourier transform (DFT) cannot be calculated in faster time than $N \log N$?

As the title says, why is it so difficult to prove that the discrete Fourier transform (DFT) cannot be calculated in faster time than $O(N \log N)$? This is a famous open problem in mathematics/...
3
votes
1answer
181 views

If P=NP, then NP = coNP. Why is this so?

I read that if we assume that P = NP, then NP = coNP. I am unable to understand why this is so.
11
votes
1answer
625 views

Why is factorization of large number hard

Why factoring a number is difficult compared to finding out if it is prime (which can be done in polynomial time) ? I would think they might be of similar difficulty in terms of computational ...
2
votes
1answer
88 views

Unknown symbol '#' in set

I am reading a text on Complexity theory. There is a set whose notation I cannot understand: "Let $\sum$ = {0,1,#}" From the context, and given that the book is used computer science courses, it ...
3
votes
1answer
123 views

Showing that #SAT is NP-hard

I need some hints to solve the following problem. (from Complexity and cryptography by Talbot and Welsh, chapter 3, exercise 3.6) Let #SAT be the function, mapping Boolean formulae in CNF to $\...
2
votes
0answers
257 views

Polynomial Time Root Extraction

Given a consistent system of polynomial equations: $A_1(x_1, x_2, x_3 ... x_n) = 0$ $A_2(x_1, x_2, x_3 ... x_n) = 0$ etc... $A_n(x_1, x_2, x_3 ... x_n) = 0$ If we let $d_1, d_2, d_3... d_n$ be the ...
2
votes
0answers
133 views

Finding a matching to connect subsets of vertices

I'm studying a graph problem which, strangely, has applications in bioinformatics. I'm not asking for a solution, but rather for advice as to whether something similar to what I do has been studied ...
0
votes
0answers
205 views

Mathematical reason for 2-player turn-based games

I've been reading Games, Puzzles, and Computation which analyzes games through game theory and complexity theory. The authors introduce something called "Constraint Logic" as a way of modeling games ...
2
votes
2answers
889 views

How to reduce 0-1 knapsack to knapsack-like problem with overflow?

Consider a knapsack-like problem where there is a set of items, and each item has a cost $c_i$ and value $v_i$. The goal is to find a subset $S$ that minimizes $\sum_{i\in S}c_{i}$ with the constraint ...
0
votes
1answer
48 views

Complexity of bounded 2-player game

I was reading about bounded 2-player games in chapter 6.1 of Games, Puzzles, and Computation. "Bounded" here means theres some finite resource of the game which imposes a limit on the number of player ...
0
votes
0answers
27 views

Vertex Set Optimization

I have the following problem: Min $c^Tx$ Subject to: $Ax = b$ $x >= 0 $ Where A is an M x N matrix: But rather a single solution I would like to know the first K best solutions where $1<= ...
0
votes
0answers
33 views

A computational complexity problem

Consider $n$ arbitrary (but fixed) unit-norm vectors $\mathbf{x}_1,\ldots,\mathbf{x}_n$ in, say, $\mathbb{R}^d$. Let $\beta>0$ be fixed. For $\mathbf{y}\in\mathbb{R}^d$, define the binary ...
0
votes
1answer
44 views

Converting Maximum TSP to Normal TSP

Consider the Travelling Salesman Problem: Given N cities connected by edges of varying weights. Given a city A what is the shortest path for visiting all the cities exactly once that returns back to ...
6
votes
3answers
279 views

Which is easier to work out: determinant or inverse?

Suppose $A\in M_n(R)$ be a $n\times n$ matrix over some ring $R$. Which of the following two tasks is easier? to work out $\det(A)$; to work out $A^{-1}$. More specifically, I want to know the ...
1
vote
1answer
689 views

Absolute value optimization

If you have an LP Maximize/Minimize: $c_1|x_1| + c_2|x_2| ... c_n|x_n|$ Subject to: $Ax = b$ Can this be solved in polynomial time with respect to the amount of data used to represent the problem?...
2
votes
1answer
166 views

How much slower is a Turing Machine if you only give it one end of the tape to work with?

Turing Machines start with the input string and tape head in the "middle" of a tape that extends infinitely in either direction. Suppose instead that the tape head starts at the "far left" of the ...
0
votes
2answers
92 views

How to work out the inverse matrix $A^{-1}$ ?

Suppose A is a matrix over some ring R (might be non-commutative). How to work out the inverse matrix $A^{-1}$?
8
votes
1answer
506 views

efficient summation of $\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}\sum_{l=1}^{n}A_{ij}A_{ik}A_{il}A_{jk}A_{jl}A_{kl}$

I want to find an efficient algorithm for calculating a sum of products with entangled indices. For example, $\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n} A_{ij}A_{jk}A_{ki}$, where $A_{ij}$ is the a $i$...
2
votes
0answers
121 views

Quadratic Diophantine Equations in Polynomial Time

Considering the problem of finding lattice points $(x_1, x_2 ... x_n)$ that satisfy a quadratic law: $F(x_1, x_2... x_n) = 0$ such that $F(x_1, x_2... x_n)$ is a second degree polynomial It is ...
1
vote
1answer
158 views

$\Sigma_k^\text{P}$−SAT definition is not clear to me

I don't understand if by saying there are $k$ alternating quantifiers on the variables $x_1$,$x_2$...$x_k$, It means we quantify ALL variables (there are only $k$ variables in the SAT formula) or just ...
1
vote
1answer
92 views

What sequences / algorithms does $O(N \log\log N)$ limit?

Considering the big-o-notation, there are a variety of algorithms that have the $O(N \log N)$ computational complexity; such algorithms are for example the merge sort, fast fourier transform, etc. ...
2
votes
0answers
132 views

Comparing two character tables

Suppose that you are given two finite groups, for example, via their Cayley tables. One can efficiently compute their character tables (efficiently = polynomial time in the order of the group), this ...
1
vote
1answer
37 views

Finding the complementary language of a given language

I'm trying to figure out what's the complementary language of: L = {w#w : w∈{a,b}*, |w| = k} I think it's the language of all the words w#w where |w|!=k. I think my answer is not correct. How ...
2
votes
1answer
135 views

What does noncomputable really mean?

I believe I understand the definition of a noncomputable problem from an introductory computer science class, but I don't understand what it really means. One of my hypothesis was that a ...
9
votes
1answer
153 views

Homomorphism for a fixed graph NP-complete?

Let $G$ be the following Graph: We want to decide whether for an input structure $\mathcal{S}$ there exists a homomorphism $S \to G$. We will call this problem $HOM_G$. The task at hand is to show ...