Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (2)

2
votes
1answer
48 views

Hardness of problem related to number of subsets that satisfy a particular property

I have the following algorithmic problem. I am given a set of elements. Each element has a set of properties. For example: ...
2
votes
1answer
27 views

About the definition of “differential privacy” in communication complexity

In the context of communication complexity I see a definition of differential privacy which isn't totally clear to me as to why it makes sense. So the two parties $A$ and $B$ draw two strings $X$ ...
4
votes
1answer
42 views

Is L closed under linear-time reductions?

L is as usual the complexity class DSPACE($\log n$), of languages decidable using a deterministic Turing machine using logarithmic workspace. Is L closed under linear-time reductions? It is ...
6
votes
1answer
76 views

Are there any non-naive parallel sparse matrix multiplication algorithms?

I was wondering about a problem in analyzing a social network (counting friends-in-common between all pairs of members) that requires squaring its adjacency matrix, and started reading up on ...
0
votes
0answers
13 views

Renyi entropy and differential privacy

In an $(\epsilon,0)$ differential privacy mechanism what does the $\alpha-$Renyi entropy of the output measure? What does it signify about the mechanism?
1
vote
1answer
43 views

How is a communication protocol a mechanism?

Given a finite set $\Sigma$ and a positive integer $n$, a mechanism is a set $\{ \mu_x \vert x \in \Sigma^n \}$ such that $\mu_x$ is a probability measure on some $\sigma-$algebra for each $x$. Now ...
0
votes
0answers
18 views

Counting words: performance of loop vs. list comprehensions [duplicate]

I am no computer scientist, so I can be naively missing some commonly implemented optimization strategies but... Looking at two ways of counting words in a text (shown below), I tend to think that ...
5
votes
3answers
247 views

Why is the addition function exponential for k-bit integers providing only zero, equality and the successor functions?

I'm currently reading the elements of programming book and have come across a section I don't quite understand A computational basis for a type is a finite set of procedures that enable the ...
1
vote
1answer
40 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 ...
0
votes
0answers
39 views

Which of the two properties isn't satisfied?

Show that the following sequence of function $\Phi_n$ is not a measure of complexity: $\Phi_n(x)=\left\{\begin{matrix} \text{ nr of commands } m \text{ that TM } T_n \text{ executes with ...
2
votes
0answers
21 views

Cobham's characterization of FP

Does anyone know of an accessible introduction to Cobham's model independent characterization of FP and it's equivalence to the standard definition using Turing machines? The best source I could find ...
0
votes
1answer
35 views

Complexity calculation using a recurrence relation [duplicate]

I just can't solve this problem, I'm new to reccurences. I have this recurrence $T(n)=n*T(n-1)$ $T(1)=1$ The second term will be: $T(n-1)=(n-1)*T(n-2)$ And so on. It's complexity is O(n!) but i ...
3
votes
1answer
259 views

If one-way functions exist are we definitely using them?

I know that if one-way functions exist then there are certain universal one-way functions that exist, but to my knowledge they are too impractical to implement (which is the main reason why they are ...
4
votes
1answer
41 views

Constructing languages in NPI other than through Ladner's Theorem

I have seen proofs of Ladner's theorem which detail the construction of languages in NPI assuming P $\neq$ NP. However, I was wondering if there are any other constructions using the fact that sparse ...
1
vote
0answers
59 views

Suppose P = NC - what then? [duplicate]

Suppose tomorrow someone discovered a proof that P = NC. What would the consequences for computer science research and practical applications be in this case?
6
votes
0answers
67 views

P vs NP and the Time Hierarchy

Assuming P $\neq$ NP, is it possible that there exists a $k$ such that for all $j$, $\textsf{DTIME}(t^j) \subseteq \textsf{NTIME}(t^k)$? There reason I ask is that I assume P = NP implies that for ...
-1
votes
1answer
29 views

What is the relation between differential-privacy mechanism and entropy?

Why do differential-privacy people care whether or not the noise function saturates the lower bound of Shannon entropy? For example : Laplace distribution that is used to model the noise function ...
6
votes
2answers
65 views

Complexity-theoretic difficult of checking the value of $\pi(x)$?

The prime-counting function, demoted $\pi(x)$, is defined as the number of prime numbers less than or equal to $x$. We can define a decision problem from $\pi(x)$ as follows: Given two numbers ...
9
votes
1answer
1k views

Why do Shaefer's and Mahaney's Theorems not imply P = NP?

I'm sure someone has thought about this before or immediately dismissed it, but why does Schaefer's dichotomy theory along with Mahaney's theorem on sparse sets not imply P = NP ? Here's my ...
1
vote
1answer
45 views

Do problems in P only reduce to NP and coNP problems?

Consider the languages $B,C,D$, such that $B\le_p C$ and $B\le_p D$. Statement: $B\in P, D\in NP, C\in coNP$. Is the statement true for every $B,C,D$? I know that the answer is no and I have ...
0
votes
0answers
26 views

NP-Hard vs NP-Complete Why NP-complete so important? [duplicate]

A problem $L$ is NP-complete when:- $L\in \text{NP}$ For every problem $L' \in \text{NP}$, $L'$ is polynomial time reducible to $L$ When at least property 2 is satisfied for a problem $L$ (but ...
-1
votes
1answer
35 views

Why is it true that $NP \ne coNP \implies X = \emptyset$?

Let the class of languages $$X = \{ L \ | \ L\in NPC \land L\in coNPC\}$$ Why is it true that $NP \ne coNP \implies X = \emptyset$?
1
vote
2answers
49 views

$A$ is finite, $B$ is NPC - When there's a polynomial reduction from $A$ to $B$?

$A$ is finite, $B$ is NPC - When there's a polynomial reduction from $A$ to $B$? Basically, I've understood that if $A$ is finite, then there's a reduction for every $B$ which isn't trivial ...
1
vote
0answers
50 views

Calculating Time Complexity of Quadratic Diophantine Equation

The particular quadratic Diophantine equation: $$ R(a,b,c) \Leftrightarrow \exists X \exists Y :aX^2 + bY - c = 0 $$ is NP-complete. (a, b, and c are given in their binary representations. a, b, c, ...
2
votes
2answers
74 views

What is practical difference between NP and PSPACE-complete?

Here's something that has puzzled me lately, and perhaps someone can explain what I'm missing. Problems in NP are those that can be solved on a NDTM in polynomial time. Now assuming P$\,\neq\,$NP, ...
1
vote
1answer
53 views

Prove that $S_2$ is closed under union and complement

I'm having trouble proving that $S_2$ is closed under union and complement, even though in this Wikipedia article it says that: It is immediate from the definition that $S_2$ is closed under union ...
1
vote
1answer
19 views

Solving the graph colourability problem in polynomial time if the equivallent decision problem is in $P$ [duplicate]

For the graph colourability problem, we are given a graph and our goal is to find a colouring of the graph with the fewest possible number of colours so that no two adjacent vertices have the same ...
3
votes
0answers
41 views

Why are decision problems easier than the equivallent optimization problems?

Suppose that we have an optimization problem defined as follows: $OPT$ = Given an input string defining a set of feasible solutions $F$ and an objective function $f$, find $x\in F$ maximizing $f(x)$ ...
0
votes
0answers
30 views

if P=NP then $L\leq L'$ for all languages [duplicate]

How can I prove that if P=NP then for each non-trivial language $L,L'\in NP$ there exists a polynomial reduction $L\leq L'$?
3
votes
1answer
47 views

Multiple FPT Parameters

The class $FPT$ (fixed-parameter tractable) is defined here. However, there is only one "parameter" that is studied from the given problem/language. Is there an equivalently defined class that can ...
4
votes
3answers
143 views

Could an NP-hard problem have a mechanical or physical solution method?

Is there any NP-hard problem that we can find a mechanical "polynomial time" solution to? For example, suppose we construct a graph out of something physical, e.g. we have have pipes through which we ...
3
votes
2answers
113 views

How can P=NP relate to creativity and proof automation, as said by Scott Aaronson?

I read several times of Scott Aaronson saying that P=NP implies that human creativity is boring and something like that, and that P=NP has something to do with proof automation. I don't get his ...
1
vote
1answer
25 views

(operationalizable) Cost measure for small problems

For what I know of complexity measures in CS, they are aimed at rather large problems. With today's computing power, most people don't care about comparing the complexity of simple problems as they ...
3
votes
1answer
46 views

Computational complexity of function $U^V$ [duplicate]

Given $(U,V)$ two integers of finite size, I have a question about the complexity of calculating the $V^U$, i.e. $V$ raised to the power $U$. Is their a polynomial time algorithm to do this? If not is ...
1
vote
1answer
50 views

Is computing 2^n NP-complete problems EXPTIME or NEXPTIME complete? [closed]

Given a NP-complete problem $A$, with parameter $a$ and a problem $B$ with parameter $b$, such that a problem in $A$ of size $\mathcal{O}(2^a)$ is $\mathcal{O}(b)$ when translated to $B$, is $B$ ...
2
votes
1answer
67 views

Prove Vertex-Cover of maximum degree 3 is NPC

This is a homework question. I need to prove that the following language is in NP Complete: 3-VERTEX-COVER = $\{\langle G,k\rangle \mid$ G is an undirected graph, each vertex in $G$ has at most ...
12
votes
3answers
918 views

Why is the class NP-Complete important compared to NP-hard?

I'm studying computational complexity and I was wondering why the NP-Complete (NPC) problems is an important class at all. I find it obvious why we're interested in showing a given NP problem is ...
6
votes
1answer
71 views

Algorithm to compose identity from a set of permutations

Given a subset P of all the possible permutations of a fixed set of elements, is there a non-exponential or optimized algorithm for computing the smallest composition of P that yields the identity ...
1
vote
1answer
46 views

Quadratic Diophantine equation - Polynomial Time Cases

In number theory, solving a Quadratic Diophantine equation (a, b, c constants) $$ a*x^2+b*y= c $$ is an NP-Complete problem. Even for a=1, the problem remains NP-Complete. The solution (x, y) are ...
2
votes
1answer
36 views

A Query regarding Quadratic Residuocity Problem

In number theory, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that: $$ x^2\equiv q \pmod{n}. ...
2
votes
1answer
74 views

A particular complexity

Whats is the name for a complexity like $n^{\log \log n}$ ? Is this exactly subexponential, or less than that ?
7
votes
1answer
99 views

Is the closure of P under e-free homomorphisms equal to NP?

The context free languages can be obtained as the closure of the Dyck language under the cone operations. The Dyck language $D_2$ is a deterministic context free language, and the cone operations ...
1
vote
1answer
85 views

Is this problem NP-hard?

Good day. Subset sum selection problem is NP-hard. I trying to solve following problem: Input: a grid NxN and subset size K and radius R. Every entry in grid contains a value. Solution: subset of ...
1
vote
1answer
34 views

Ordered knapsack problem?

I'm trying to find the name of this problem, and with it a reasonable algorithmic solution. Setup: There are $n$ items with weights $w_1,\dots,w_n$, and $m<n$ buckets with target weights ...
3
votes
1answer
63 views

Intuition for PH notation in Arora-Barak's Computational Complexity

For the definition of polynomial hierarchy: $x \in L \Leftrightarrow \exists u_1 \in \{0, 1\}^{q(|x|)}\forall u_2 \in \{0, 1\}^{q(|x|)} \cdots Q_i u_i \in \{0, 1\}^{q(|x|)} M(x, u_1, \ldots, u_i) = ...
2
votes
1answer
28 views

Ford-Fulkerson Running Time

This question might be really basic but every source seems to skip over a couple of steps neither of which seem trivial to me. It would be great if someone could explain them! In the analysis of ...
1
vote
1answer
98 views

Can Circuit Value Problem or HORN-SAT be reduced to PATH problem?

PATH = {(X,R,S,T) | exists an x in S that is admissible} Where R is a relation of X x X x X, S is a unary relation of X and T is a unary relation of X aswell. An x element of X is admissible if it is ...
1
vote
1answer
84 views

How important is it to find a deterministic polynomial time algorithm to construct Ramanujan graphs? [closed]

As in I don't know what is the difference between say the conferences SODA, STOC or FOCS. Measured in terms of such conferences, where would such a result be publishable? This is not a "technical" ...
4
votes
1answer
46 views

What usage is the delta defined in the polynomial hierarchy?

At the Wikipedia page, the polynomial hierarchy also defines the following: $\Delta_0^\text{P} = P$, $\Delta_i^\text{P} = \text{P}^{\Sigma_{i-1}^\text{P}}$ However, the only usage of this anywhere ...
0
votes
0answers
15 views

Arthur-Merlin protocol to decide a set size

Please look at the example here at the bottom of page 3, http://www.cs.nyu.edu/~khot/CSCI-GA.3350-001-2014/sol3.pdf Here it seems that the set whose size Arthur is trying to approximate is known in ...