Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

Filter by
Sorted by
Tagged with
1
vote
1answer
36 views

Why exactly is Zero Knowledge Proof used here?

"The Ali Baba cave" example of ZKP is pictured below. There is no need for a probabilistic ZKP protocol to prove to the verifier of the statement (that the prover has the key to the door). ...
0
votes
0answers
14 views

Limited number of calling for a decision blackbox to compute all the solutions

I am trying to reduce between a solution problem and a decision version of the same problem. The problem is the orthogonality problem. Given $2$ sets $L$ and $R$, whose size each is $n$ vectors over $\...
1
vote
0answers
16 views

Are there more efficient recognizers for the halting problem?

Define the halting problem as $\{\langle M, w\rangle: \text{$M$ is a TM that halts on $w$}\}$. It is undecidable, but recognizable, with a naive recognizer that simulates $M$ on $w$. In a certain ...
0
votes
0answers
13 views

Turing machine with polynomial complexity on Jflap

I would like to ask a question: I have this very simple Turing machine. Simply by subtracting the numbers A and B, given the input M (A, B, C, D) =. Using the Step function on Jflap, complete the ...
0
votes
0answers
22 views

Sum of asymptotic notations

Let's consider a function $f \in \Theta(h)$ and a function $g \in \omega(h)$, what could I conclude about the sum $f + g$? Since $f \in \Theta(h)$ I think about $f$ as if it grows just like the ...
3
votes
0answers
30 views

Linear time complexity

We know from the linear-speedup-theorem that NTIME($\mathcal{O}(f)$) = NTIME($f$) and DTIME($\mathcal{O}(f)$) = DTIME($f$), given that $f(n) > (1+\varepsilon) n$ for some $\varepsilon\in\mathbb{R}$....
0
votes
0answers
25 views

Modern proof of Goldwasser-Sipser IP[n]=AM[n+2]?

The original paper by Goldwasser and Sipser proved IP[Q(n)]=AM[Q(n)+2]. Is there some modern source that proofs the theorem? (The full theorem and not specific cases such as limiting the number of ...
1
vote
1answer
40 views

find 3 points among some given 2D points such that the triangle includes another given point

Ideally, these would be the points that form the smallest (nondegenerate or degenerate) triangle. However, I can admit a large amount of approximation to get it to a lower order of complexity. I can ...
1
vote
1answer
37 views

Why is SET PACKING in NP?

I have seen an lot of proves why SET PACKING is NP complete. However, in every prove it states that SET PACKING is clearly in NP. It might be a stupid question, but is not so clear to me. I see that ...
1
vote
0answers
19 views

Conflict Clusters – Another P=NP Proof [closed]

Conflict Clusters – Another P=NP Proof Exactly 1 in 3 SAT ($X3SAT$) is a variation of the Boolean Satisfiability problem. Given an instance of clauses where each clause has three literals, is there a ...
2
votes
1answer
52 views

Maximum independent subset for graphs with lots of edges

Consider an NP-hard graph problem, like the maximum independent set problem. Let us say I restrict my inputs to only be graphs that have $n$ vertices and at least $n^{c}$ edges, for some $c > 1$. ...
3
votes
1answer
62 views

Can it be NP hard to calculate the value of a function?

So, I've just begun dabbling in complexity theory and I'm somewhat confused as to the relationship between NP-hardness and function computation. As far as I've understood, NP-hardness is defined for ...
1
vote
1answer
40 views

Does a set definition have computational complexity?

I'm wondering if a mathematical set definition has a computational complexity. For example, assume I have some kind of problem where the solution is given by the positive integers smaller than a given ...
2
votes
1answer
27 views

Reducing a CNF formula to a DNF formula in less than exponential time

The easy way is by looking at the $\{0,1\}$-table and construct the corresponding DNF formula from that, but this will take $2^n$ time. I want to do it much more efficiently. My idea is based upon the ...
1
vote
1answer
17 views

A query regarding Definition of Circuit Family and Languages

This is a query regarding the definition of Circuit Family and Language (in the same Context). The textbook definitions of each are: Language: A function whose inputs and outputs are a finite bit of ...
1
vote
0answers
25 views

Graph based on strings of turing machine

For a $\Sigma$ with characters $0,1,$#$,\sigma_1,...,\sigma_m$. I have any $M$ that is a deterministic turing machine. Fix a $n$ (natural). i look at the following graph constructed from the turing ...
1
vote
1answer
15 views

Is there a known relationship between Kolmogorov Complexity of a binary string and the logic optimization of the corresponding Boolean function?

I haven't thought about how to go about proving it or finding a counterexample (I probably don't have the right background), but it seems intuitive to me that, given some representation of a Boolean ...
4
votes
1answer
68 views

Attempt to reduce to problem of inner product

The problem of Orthogonality: gives $n$ vectors of dimension $k$ and another set of same, can a pair be found with inner product = $0$? The problem of max product: likewise two sets each $n$ vectors (...
1
vote
1answer
53 views

Whether and how to distinguish two kinds of $O(1)$ speedup

Here is a very bad algorithm that computes $4n$ for an integer input. ...
2
votes
2answers
88 views

What if solving P vs NP revealed a contradiction?

Let's just say that some person discovered that $P = NP$ implies $P \neq NP$ and $P \neq NP$ implies $P = NP$, and we don't know what is causing this contradiction, And this was a valid proof that was ...
1
vote
2answers
41 views

What are some problems in EXP not known to be EXPTIME-Complete, but also do not have any known algorithm in NP?

These would be problems known to be in exp where there could hypothetically be a P or NP algorithm, but none have been discovered yet if one is possible.
-2
votes
2answers
172 views

What are some problems in EXPTIME not known to be EXPTIME-complete?

Not problems like chess. I'm thinking problems that would be very useful to be able to solve in sub-exponential time. These would be problems not known to be EXPTIME complete. Edit I mean problems ...
0
votes
1answer
36 views

Combination of two Languages in a arbitrary complexity class

Given two unrelated languages $L_0$ and $L_1$ contained in some complexity class $C$. Is the language $L_x=L_0\times L_1= \{(x,y)|x\in L_0, y\in L_1\}$ always contained in $C$? And if that is the case,...
0
votes
0answers
18 views

NC with nearest neighbor gates

Consider a circuit belonging to the class $\text{NC}^i$, as defined here. From my understanding, the circuit consists of AND, OR ar NOT gates, each of bounded fan in --- without loss of generality, ...
0
votes
1answer
27 views

Sum of a function Θ(g) with a function that is not O(g)

Consider g a function of n: $g(n)$. Knowing that the function $f(n) \in Θ(g(n))$ and the function $h(n) \notin O(g(n))$, could we conclude anything, related to it's asymptotic behaviour, about $f(n) + ...
1
vote
1answer
39 views

Importance of $\Sigma^P_2=PSPACE$

Assuming (the unlikely scenario) that the Polynomial Hierarchy collapses to second level. Thus, $\Sigma_2^p=PSPACE$. How significant this result would be (broad consensus) as compared to the other ...
5
votes
1answer
486 views

Why are $\sf{P} \ne \sf{NP}$ and $\sf{NP} \ne \sf{coNP}$ compatible?

If $\sf{P} \ne \sf{NP}$ and $\sf{NP} \ne \sf{coNP}$ are both true then $\sf{P}$, $\sf{NP}$ and $\sf{coNP}$ are three separate complexity classes. In other words, verifying a solution, finding a ...
3
votes
1answer
55 views

Relation between $P$ vs $\mathit{NP}$ and $P^{\mathit{NP}}$ vs $\mathit{NP}^{\mathit{NP}}$ questions?

Given that both $P \subset \mathit{NP}\ ?$ and $P^{\mathit{NP}} \subset \mathit{NP}^{\mathit{NP}}\ ?$ are open questions. Is it possible that $P \subset \mathit{NP}$ and $P^{\mathit{NP}} =\mathit{NP}^{...
0
votes
0answers
38 views

pseudo-dimension for knapsack problem

Let $v_i, s_i$ be the value and size of item $i$, let $\rho \in \mathbb{R}$, n be the maximum number of items. Then we add items based on $\frac{v_i}{s_i^{\rho}}$ in decreasing order. I was trying to ...
30
votes
1answer
3k views

Problems that are polynomially "hard" to compute but "easy" to verify

In the (unlikely) event that $P=NP$ with a constructive proof of a polynomial time algorithm that solves 3SAT, obviously things will be very different. However, practically, it could happen that the ...
1
vote
1answer
20 views

Can I reduce from the recognition version of one probem to another without knowing the exact parameter?

I was reading the paper "Kou, L. T., Stockmeyer, L. J., & Wong, C. K. (1978). Covering edges by cliques with regard to keyword conflicts and intersection graphs. Communications of the ACM, 21(...
0
votes
1answer
29 views

Help in proving L-Completeness

I'm trying to prove that the following language is L-complete A is a language where each word is comprised of 0s and 1s & the number of 0's is double that of the number of 1's So far I've managed ...
0
votes
1answer
32 views

What would be the conseuqences of BQP = NEXPTIME?

On wikipedia it says that $BQP ⊆ EXP$. However it is not known if $BQP \subset EXP$ Also I've seen that $PSPACE$ could contain $NEXP$ and does contain $BQP$. For this were assuming the incredibly ...
1
vote
2answers
57 views

What's wrong with the reduction from integer programming to linear programming?

I'm confused with polynomial-time reduction and NP-hardness. Let's say that the following integer programming is NP-hard. $\min_{x \in K} f(x)$, where $K$ is a finite subset of $\mathbb{N}$. But it is ...
1
vote
2answers
35 views

We cannot recognize a set of languages as the language themselves

"We cannot recognize a set of languages as the language themselves" What is the meaning of the line and why we cannot do it and how is the encoding of TM is helping in that?
0
votes
0answers
35 views

Algorithm for the specific problem

A problem : Given a string of number in base $10$ we want an algorithm to calculate the number of numbers, where we replace (only) a single digit to produce a number so that that number is divisible ...
2
votes
0answers
32 views

Non-trivial reduction form SAT to $3$-SAT

Looking for any idea for reduction from $SAT \leq 3-SAT$ where $SAT$ is known to have $d$ variables at most in each clause. I am looking for a reduction in which the resulting formula will not depend ...
1
vote
0answers
19 views

Finding square root of a gram matrix over the integers [closed]

Suppose that matrix A is a symmetric positive definite matrix over the integers, i.e., $A \in Z^{n\times n}$, if B is a matrix over the real numbers, it is not difficult to find B such that $A = B \...
1
vote
0answers
44 views

Algorithm to find maximum sum over weighted overlapping intervals

Suppose we are given n open intervals $(a_1, b_1), ..., (a_n, b_n)$, with interval $i$ being assigned a weight $w_i$ for all $i$. Define a "good subset" of intervals to be a subset of those $...
6
votes
1answer
117 views

Prove TILING is NP-Complete

I have a homework task to show that $\mathrm{TILING} = \{(T, 1^N) \mid \text{it is possible to cover } N \times N \text{ square with tiles from }T\}$, where $t\in T$ is $C^4$ for some color set $C$, ...
1
vote
1answer
36 views

Is Self-Modifying Turing Machine equivalent to NTM or TM?

Let SMTM be Turing Machine, but the commands recorded in which can change to others in some random way (for example, choose with a 50/50 probability the command to move to the right or move to the ...
0
votes
1answer
28 views

What are some examples of problems in R but not in PR?

Also are there any R complete problems? These would be the hardest decidable problems to my knowledge. Sorry if this isn't specific enough.
3
votes
1answer
141 views

A complexity class between P and FPTAS

The question is about approximation algorithms to NP-hard optimization problems. For concreteness, let $M$ be a minimization problem with $n$ inputs, where all inputs and outputs are integers in the ...
1
vote
1answer
25 views

About NP-completeness and reduction

Probably this is a basic question but I'm not sure how to finish this proof. I have a problem $X$ and I want to prove that it is possible to reduce $X$ to another problem $Y$. I know that $Y$ is NP-...
2
votes
1answer
35 views

find vertex cover of size at most 30 of a graph

This is a question from an exam I got wrong. Given an undirected graph $G$. Consider the decision problem of finding if there exists a vertex cover of size at most 30. Can we find a polynomial time ...
1
vote
0answers
22 views

How to show perfect completeness of the Set Lower Bound Protocol?

In these lecture notes (on page 5 under "Some Remarks") it is claimed that the Set Lower Bound Protocol (given there on page 4) can be modified to have perfect completeness. However, while I ...
2
votes
1answer
12 views

Question on worst-to-average-case reductions

Consider two decision problems A and B. We know that A reduces to B in polynomial time --- if we could solve B, we have a procedure to solve A. Now, let's say it is known that the worst case instances ...
-2
votes
2answers
107 views

If the halting problem is NP hard, would P = NP with a hypercomputer capable of computing the halting problem in polynomial time?

The halting problem is NP hard, to my knowledge any NP problem can be reduced to a NP hard problem. Let us define a new computational complexity class called HP(Hypercomputational polynomal-time), The ...
2
votes
0answers
26 views

On the complexity of equitable $k$-coloring split graphs

The Wikipedia article on Equitable coloring states that A polynomial time algorithm is known for equitable coloring of split graphs. The referred paper also seems to achive the proposed polynomial ...
0
votes
0answers
15 views

Bin packing (NP-Complete)

I'm working on a project over Bin packing being NP complete, I understand the full reasoning behind it (algorithmically), but I need to know what's a proper explanation for the Bin packing being NP ...

1
2 3 4 5
96