# Tagged Questions

Questions related to the (computational) complexity of solving problems

42 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 ...
56 views

47 views

### How to prove intersection between languages L1 (belongs to NP) and L2 (belongs to P) actually belongs to NP?

I have to prove that if L <=p L1 intersection L2, where L1 and L2 are described as above, L belongs to NP. I thought about the definitions of P and NP and built a DTM D that decides L2 and a NTM N ...
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-...
66 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 ...
121 views

### How can I efficiently find the optimal order to apply special offers to a shopping cart?

Given a list of items which represent items in a shopping cart, and a list of available special offers which replace one or more regular items to lower the cost of those items, how can I decide the ...
89 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 ...
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 ...
36 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 ...
33 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 ...
81 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 ...
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 ...
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 ...
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 ...
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: ...
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.
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 ...
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 ...
25 views

186 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 ...
135 views

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 ...
357 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 ...
90 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, ...
99 views

### Variants of the 3-Partition problem

The 3-Partition problem (wiki) is a $\text{NP}$-complete problem which is to decide whether a given multiset of integers can be partitioned into triples that all have the same sum. It is well-known ...
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 ...
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 $$... 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 ...
Logical Min Cut (LMC) problem definition Suppose that $G = (V, E)$ is an unweighted digraph, $s$ and $t$ are two vertices of $V$, and $t$ is reachable from $s$. The LMC Problem studies how we can ...