Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (3)

1
vote
0answers
17 views

Computational Complexity of Exponential Expression Divisibility?

Garey and Johnson mentions the problem of 'Exponential Expression Divisibility" as "Not known to be in NP or co-NP, but solvable in pseudo-polynomial time using standard GCD Algorithms". Pseudo-...
0
votes
0answers
38 views

Is there a philosophical counterpart question to P != NP?

Gödels motivation to prove his incompleteness theorems was the philosophical statement "This sentence is wrong.". Is there a philosophical counterpart to the statement P != NP? For example such ...
2
votes
1answer
38 views

Negligible functions in definitions of statistical closeness and computational indistinguishability

Statistical closeness implies computational indistinguishability. Is there any (simple) relationship between negligible function that is used in definition of statistical closeness and negligible ...
7
votes
2answers
72 views

Why is first-order logic (without arithmetic) VALIDITY only recursively enumerable, and not recursive?

Papadimitriou's "Computational Complexity" states that VALIDITY, the problem of deciding whether a first-order logic (without arithmetic) formula is valid, is recursively enumerable. This follows from ...
0
votes
1answer
65 views

AC-3 Algorithms on CSP problem, What is happened when enocunter to an empty domain variable?

Suppose We Applying Arc-Consistency (AC3) algorithms on one Constraint Satisfaction Problem, if domain of one variable be empty, what is the next step of this algorithm? According to This Link and ...
0
votes
1answer
56 views

Does the fact that there exists a polynomial time quantum algorithm for integer factorization suggest that integer factorization is in P?

Just as the title says: Does the fact that there exists a polynomial time quantum algorithm for integer factorization suggest that integer factorization is in P? Additionally, if one could show that a ...
-1
votes
0answers
22 views

Prove that all P problems except {} and {a,b}* are complete [duplicate]

It is easy to say that {} and {a,b}* are not P complete because other problems in P can't be reduced to these because ...
2
votes
2answers
36 views

Does 'subexponential algorithm' refer to input or number of bits used to represent input?

When an algorithm is said to be subexponential - does this refer to the input N or the number of bits used to represent N? Consider the following: trial division for integer factorization (i.e. try ...
3
votes
1answer
30 views

The class of languages that can be certified in a small amount of space

NP can be characterized in two different ways, one of them is that it's the class of languages that can be certified by a witness in a polynomial time. I wonder, if we consider the same notion but ...
5
votes
1answer
71 views

Why do we reject turing machines that use space less than the log of the length of the input?

In Computational complexity: Modern Approach by Arora and Barak, it's mentioned that We will require however that $S(n)> \log n$ since the work tape has length $n$, and we would like the ...
0
votes
1answer
25 views

General number field sieve is slower then exhaustive search for 'small' numbers?

In an attempt to understand the efficiency of the GNFS, I've been looking at runtimes. The calculations seem to indicate the GNFS runs slower than exhaustive search for smallish n. For example: ...
1
vote
1answer
32 views

Label coloring to maximize number of “balanced” triangles (NP-hardness)

Define a triangle in undirected graph $G$ is balanced if the edge labels in the triangle are $(+1, +1, +1)$, $(-1, -1, +1)$, $(+1, -1, -1)$ or $(-1, +1, -1)$ (social balance theory). Problem ...
0
votes
1answer
35 views

Why does using unary in subset sum problem result polynomial time complexity?

From my understanding, the complexity of the algorithm is O(number of inputs * number of bits for input). The number of bits in binary notation is obviously less ...
2
votes
1answer
25 views

Is the runtime for the general number sieve given in base 10, e or 2?

When the runtime of the GNFS is given as e^(64/9*b(log b)^2)^1/3, what base is the log? I'm assuming its e, but other options would obviously be 10 and 2.
3
votes
1answer
14 views

Using oracle machine to speed up tree solution search

Let $P$ be a boolean problem of size $n$, thus the complete solution search space tree is of size $2^n$. Applying simple tree search for the solution will have take $O(2^n)$ operations, (for ...
1
vote
1answer
24 views

Hardness amplification of PRFs by increasing key length

I was reading the GGM construction for PRFs and wondering the relation between key length and hardness. GGM construction does not seem to yield any significant improvements. Are there any PRF ...
0
votes
0answers
25 views

Time complexity of fixed point program

Suppose $\mathcal{M}_f$ is a Turing machine that computes the total function $f(x)$ in time $T_{\mathcal{M}_f}(|x|)$. Also suppose $M_H$ is a Turing machine that computes the total function $H(n,x)=\...
0
votes
0answers
51 views

What's the complexity of the problem of optimally distribute n balls in m boxes?

Assuming that there is a function $f(x)$ (non linear, non convex) where $x$ is the vector $[n_1,n_2,\dots n_m]$ where $n_i$ is the number of balls in the box $i \in \{1,\dots m\}$, and $\sum \limits_i^...
0
votes
0answers
19 views

Why does not the result in this notes show P is not NP in BSS model?

As far as I know (not understand that well though) BSS model is a real computation model and $P_{\Bbb R}\neq NP_{\Bbb R}$ is a real analog of $P\neq NP$ problem in BSS model. The lecture notes http://...
0
votes
0answers
30 views

Consequence of P=NP in BSS model

We know that in the Valiant model the result VP=VNP would imply NP is in P/poly. Do we know any consequences in case P=NP holds in BSS model?
2
votes
3answers
204 views

Asymptotic equivalent of the recurrence T(n)=3⋅T(n/2)+n

The questions is to find the running time $T(n)$ of the following function: $$T(n)=3\cdot T(n/2) + n \tag{1}$$ I know how to solve it using Master theorem for Divide and Conquer but I am trying to ...
1
vote
1answer
33 views

How do I find running time for the following divide and conquer problem?

Question is to find the runtime $T(n)$ of following problem by solving the recurrence. $T(n)=16\cdot T(\frac{n}{4}) + n!$. I went through the following theory. If the recurrence relation is of the ...
2
votes
0answers
14 views

Uses of unary or sparse languages in other models

In the turing model we have the statements that if there is an unary or sparse language that is NP complete then P=NP and if there is a Turing reduction from an NP complete problem to an unary or ...
5
votes
5answers
179 views

Why does restricting size of input for NP complete problem imply a runtime of O(1)?

I've seen this statement mentioned a few times here on cs.stackexchange and have not been able to follow the logic. The statement is 'If you restrict the input size of the problem then solving that ...
1
vote
0answers
27 views

Single-tape Universal Turing Machine time complexity

When studying the time-hierarchy and space-hierarchy theorems, the main idea is to use a simulation by the universal TM. It is mentioned that the time bound is increased by a logarithmic factor while ...
1
vote
1answer
30 views

Is the prime factorization problem not an instance of the change making problem?

When using as the set of coins all logarithms of the prime numbers or numbers in general, and when using the logarithm of the number to be factored. The problem is just finding the logarithms that can ...
-1
votes
0answers
85 views

Complexity of Polynomial Division

Given two polynomials $A(x)$ and $B(x)$. What is a fast way to find $Q(x)$ and $R(x)$ such that $A(x) = Q(x) \times B(x) + R(x)$ (and the degree of $R(x)$ is less than degree of $B(x)$) I know that ...
0
votes
0answers
28 views

Are there any methods to quantify complexity of finite problems?

On page 348 of "Sipser M. Introduction to the Theory of Computation. Cengage Learning; 2012 Jun 27", it says Perhaps at some time in the future, methods that can quantify the complexity of finite ...
0
votes
1answer
54 views

Is this argument wrong “since DOM is special kind of RDOM, then RDOM is NP-hard”?

The domination problem $DOM$ is defined as $$ DOM = \{ \langle G,k \rangle\ | \ G \text{ has a domination of size } k, K \in \mathbb{N} \}, $$ and the rainbow domination problem $RDOM$ is defined as $$...
4
votes
1answer
88 views

is the problem of parallelising any program, NP-complete?

Consider a program written in a common language such as C. Assume that it does not have any explicit parallel constructs. Then, once it is compiled to an executable program, it will be run serially, ...
0
votes
0answers
18 views

Find reduction from Hamiltonian Cycle to Double Hamiltonian Cycle

$$DoubleHC=\{G\,| \text{G has at least two Hamiltonian Cycles}\}$$ I think about take a graph with HC and add to it two vertexes and edges to two randomally vertexes, but without success. Is my try ...
5
votes
3answers
351 views

Is Green's the best 16-input sorting network so far?

Every paper says that Green's construction is the best 16-input sorting network as for now. But why does Wikipedia says: "Size, lower bound: 53"? I thought "lower bound" meant:"If there exists at ...
-2
votes
1answer
50 views

I can find in a graph a path between two input nodes to be exactly of length k

I have in input an undirected graph and two nodes. It is possible to find a path of lenght k, where k is a constant, in polynomial deterministic times? Or this problem belongs to NPC? Thanks
4
votes
2answers
93 views

Do Oracles run in O(1) or O(n) time?

The common understanding of what oracle does is that it answers a question after a single operation. So at first glance, it runs in $O(1)$. But, doesn't it need to actually read the input? Wouldn't ...
1
vote
1answer
85 views

Problems that are easy on bipartite but hard on general graphs

Are there any problems that are easy for bipartite graphs, but hard for general graphs? I am asking because some classical problems are formulated in reference to people looking for a spouse, such as ...
0
votes
1answer
19 views

Checking membership in DFA with fixed length using AC1 circuit?

I'm supposed to find circuits , which can solve the question of membership in a regular language A with fixed length. The depth is limited by O(log(n)) and the size by O(n). Divide and Conquer should ...
2
votes
0answers
25 views

Oblivious Universal Turing Machine in O(T log(T)) time

I'm currently reading Computational Complexity: A Modern Approach. In this book, they give a proof of a universal Turing machine $U$ such that if $M(x)$ runs in $T$ steps, then $U(\lfloor M \rfloor, x)...
1
vote
1answer
101 views

Why doesn't subset sum solution violate Exponential Time Hypothesis?

The quickest algorithm for solving subset sum currently is $2^{n/2}$ (via Wiki). Why doesn't this violate the Exponential Time Hypothesis which states that “there is no family of algorithms that can ...
3
votes
1answer
35 views

Shorten Length Reduction

I've stumbled upon this Question: We say that a reduction $f$ of a language $A$ to a language $B$ is a Shorten length reduction, if there exists a number $ n\in N $ s.t for every $ w\in A $, s.t ...
0
votes
1answer
45 views

What is an example for a decidable language not in P?

I'm having trouble showing that $P\neq R$. Obviously $P\subseteq R$, but is there a decidable language which is definitely not (under all answers to open questions s.t. $P=NP$ or $NP=PSPACE$) in $P$ ?...
1
vote
1answer
43 views

Problems that are hard in the best case?

Are there any problems that are hard in the best case? In particular, I was wondering if there are problems that are NP-hard or #P-hard in the best case.
1
vote
2answers
50 views

Efficient algorithms for checking non-emptiness of the language of a Turing machine

I know that language non-emptiness is TM recognizable, and one can perform a BFS to find an input string that TM accepts, if there is any. But, what is the most efficient algorithm for that?
3
votes
2answers
109 views

What would NP-complete solution in O(2^N/B) mean?

Suppose we had an algorithm that solved an NP-complete problem (SAT, TSP, etc.) in time $O(2^{N/B})$ where $B>2$ is an input to the algorithm, along with the instance to be solved. So for $B < ...
-3
votes
1answer
65 views

proving that pp closed under cook reductions [closed]

I tried to prove or disprove that pp is closed under cook reductions. anyone has a idea or link to a answer?
4
votes
1answer
35 views

Question regarding Karp-Lipton theorem

In the proof in wikipedia, it goes like this: Let $L \in \Pi_{2}$, so we can describe membership in $L$ as a formula: $\forall_{y}\exists_{z} V(x,y,z)=1 \iff x \in L$ (where V is polynomial ...
-1
votes
1answer
44 views

when can I know if a class (complexity) is closed under reduction (cook/karp)

How do I know if a class let's say PP , is closed under cook reduction or not closed? I understand the concept of reduction (how to use it mainly) , but still can't figure out the meaning behind it, ...
3
votes
2answers
173 views

Proving that PP is closed under symmetric difference

I want to prove that PP is under symmertic difference. let A be a language in PP and B likewise. I tried showing that : (A\B) U (B\A) in PP , so by show each in PP and then showing that it's closed ...
3
votes
1answer
111 views

Meaning behind 1/ϵ in FPTAS

I am currently learning about FPTAS and PTAS but do not understand what the definition of FPTAS. A fully polynomial time approximation scheme (FPTAS) for problem $X$ is an approximation scheme ...
-1
votes
1answer
27 views

Poly-time reduction from HAMPATH to HAMPATH-E

I need to prove that HAMPATH-e = { < G,s,t,e > | G is directed graph, s, t are vertices and e a edge } there is hamiltonian path between s to t that cross the edge e is an NP complete. i've ...
2
votes
1answer
31 views

What is the proof that boolean circuit (no negation gate) can be arranged as alternating OR and AND gates

In circuit complexity theory, a branch of computation complexity theory, a theorem is that any Boolean circuit without NOT gates can be written equivalently as a hierarchical structure, in which the ...