# Tagged Questions

Questions related to the (computational) complexity of solving problems

31 views

27 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-...
63 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 ...
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 ...
88 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 ...
95 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 ...
59 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 ...
30 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 ...
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 ...
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 ...
80 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 ...
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: ...
39 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 ...
36 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 ...
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.
16 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 ...
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 ...
25 views

20 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://...
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?
205 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 ...
34 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 ...
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 ...
185 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 ...
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 ...
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 ...
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 ...
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 ...
54 views

355 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 ...
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
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 ...
86 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 ...
23 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 ...
25 views

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?
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 ...