# Tagged Questions

Computational complexity, a part of theoretical computer science that deals with understanding how efficiently a problem can be solved.

2k views

327 views

### Efficient computation of $E\left[\left(1+X_1+\cdots+X_n\right)^{-1}\right]$ with $(X_i)$ independent Bernoulli with varying parameter

Suppose we have the random variables $X_1, \ldots, X_n$ that have Bernoulli distributions with the (possibly different) probabilities $p_1, \ldots, p_n$. For example, $X_1$ = 1 with probability $p_1$ ...
341 views

### Eigenvalue test faster than $O\left(n^3\right)$?

Given a real $n\times n$ matrix $A$, one can find the eigenvalues in $O\left(n^3\right)$ by using say, the $QR$ algorithm. Now, what if we guess an eigenvalue $\lambda_0$, and we want to know if it's ...
283 views

### How to formulate the P v.s. NP problem as a formal statement inside the language of set theory?

I've read a lot that some computer scientists believe that P v.s. NP could turn out to be independent of ZFC. The thing that puzzled me is how to formulate this inside the language of set theory? I ...
326 views

### Why isn't NP = coNP?

Suppose a language L is in NP. I think that means a nondeterministic Turing machine M can decide it in polynomial time. But then shouldn't it be in co-NP, because can't we define a new Turing machine ...
638 views

### Why is factorization of large number hard

Why factoring a number is difficult compared to finding out if it is prime (which can be done in polynomial time) ? I would think they might be of similar difficulty in terms of computational ...
143 views

### How does one interpret statements like: “The traveling salesman problem is NP-complete?”

The world abounds with statements like: The traveling salesman problem is NP-complete. But when I follow try to follow the Internet's links "down the rabbit hole," I don't get a truly sensible ...
328 views

### Is there any infinite set of primes for which membership can be decided quickly?

The AKS algorithm decides whether or not $n$ is prime in time $\tilde{O}((\log{n})^6)$. I am wondering if there is any faster algorithm to determine membership in some infinite set of primes. What I ...
741 views

### Is there an easy way to find the sign of the determinant of an orthogonal matrix?

I just learned that if a matrix is orthogonal, its determinant can only be valued 1 or -1. Now, if I were presented with a large matrix where it would take a lot of effort to calculate its determinant,...
225 views

### Number of orderings of subset sums

In short: In how many ways can all $2^n$ subset sums of $n$ real numbers $a_1,\ldots, a_n$ be ordered? I am not concerned about the case in which different subsets sum to the same number; you may ...
664 views

### If $P \ne NP$, is every language not contained in $NP$ $NP$-hard?

The other day, a student asked me whether, if $P \ne NP$, whether any language outside of $NP$ is known to be $NP$-hard. I wasn't sure if This is definitely known to be true, This is definitely ...
941 views

### How hard is it to do arithmetic?

People in computing are often observed saying that a computation takes $\operatorname{O}(n^3\log n)$ steps or that it's NP-hard or that it's not computable, or that it's primitive recursive, etc. I ...
804 views

### Has there been a rigorous analysis of Strassen's algorithm?

According to Wikipedia, Strassen's Algorithm runs in $O(N^{2.807})$ time. Has anyone seen a more rigorous analysis displaying constants, possibly in a specific language such as C or Java? I ...
316 views

### Could someone prove they had a halting oracle?

Suppose someone comes to you and claims to have a halting oracle. Is there any way for you to verify the truth or falsity of their claim in finite time? If so, what constraints on the proof process ...
539 views

### Algorithm for a deck manipulation

Let's say you have a randomised deck of $N$ different cards. An $M$-action ($M\le N$) is defined as follows: you look at the top $M$ cards of the deck, put as many of them as you choose on top of the ...
271 views

2k views

### If an unary language exists in NPC then P=NP

I've a question regarding a theorem in Complexity Theory. It is said that if there exists an unary language in NPC then P=NP e.g if {1}* in NPC then the above is correct. It means that there exists ...
154 views

### Homomorphism for a fixed graph NP-complete?

Let $G$ be the following Graph: We want to decide whether for an input structure $\mathcal{S}$ there exists a homomorphism $S \to G$. We will call this problem $HOM_G$. The task at hand is to show ...
28k views

### What is the 3SAT problem? [closed]

I don't get the 3SAT problem. Can someone explain the 3SAT problem as if I were 5 years old, ideally with examples? Thanks!
1k views

### Why are Polynomial Time Problems Considered Tractable, and Larger Times are Not?

I've been reading up on $P=NP$, problem tractability, etc. Here's my question: Why is it that we consider problems that can be solved in polynomial time - or algorithms/problem-solvers running in ...
803 views

### Why does Strassen's algorithm work for $2\times 2$ matrices only when the number of multiplications is $7$?

I have been reading Introduction to Algorithms by Cormen. Before explaining Strassen algorithm the book says this: Strassen’s algorithm is not at all obvious. (This might be the biggest ...
1k views

### Divisor summatory function for squares

The Divisor summatory function is a function that is a sum over the divisor function. D(x)=\sum_{n\le x} d(n) = 2 \sum_{k=1}^u \lfloor\frac{x}{k}\rfloor - u^2, \;\;\text{with}\; u = \lfloor \sqrt{x}...
269 views

### Applications of computation on very large groups

I have been studying computational group theory and I am reading and trying to implement these algorithms. But what that is actually bothering me is, what is the practical advantage of computing all ...
578 views

### What is the relationship between ZFC and Turing machine?

I did not learn Logic properly but so far I understand that proof systems can be viewed as a kind of machine. For proof system, ZFC seems to be the most powerful one that we use so far. Similarly, for ...
13k views

### Converting to Chomsky Normal Form

I am trying to learn how to convert any context free grammar to Chomsky Normal Form. In the example below, I tried to apply Chomsky Normal Form logic, to result in a grammar, where every symbol either ...
163 views

### Proving that one has solved chess by exhibiting the zeroes of polynomials over finite fields?

My question is based on one of Scott Aaronson blog post which states that a God-like being could convinced the villagers, to any degree of confidence, that she has solved chess by answering a few ...
### efficient summation of $\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}\sum_{l=1}^{n}A_{ij}A_{ik}A_{il}A_{jk}A_{jl}A_{kl}$
I want to find an efficient algorithm for calculating a sum of products with entangled indices. For example, $\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n} A_{ij}A_{jk}A_{ki}$, where $A_{ij}$ is the a $i$...
I want to write a function that does the following: Input: An integer $n$ A function $f$ that maps nonempty subsets of $\{1, \dots, n\}$ to "yes" or "no" such that (a) every singleton set gets "yes,...