All Questions

Filter by
Sorted by
Tagged with
10 votes
1 answer
5k views

LP formulation for if-conditions

I have the following LP: /* Objective function */ min: 1 w + 2 x + 0.5 y + z; /* Variable bounds */ w + x <= T1; w + y = U1; x + z = U2; T1 = 50; U1 = 70; U2 = 25; In this case U1 + U2 > T1 and ...
Bala's user avatar
  • 211
17 votes
1 answer
2k views

Meaning of P=NP? depends on space-time geometry ?

This question is about Page 125 of the book "Cellular automata in hyperbolic spaces: Volume 2" By Maurice Margenstern, Publisher Archives contemporaines, 2008. http://books.google.com/books?id=...
Roy Maclean's user avatar
-2 votes
1 answer
237 views

Approach to implementing an STM for a student [closed]

A student has implemented a scheme interpreter in scheme and then in C, and a scheme compiler in scheme. That student is now interested in implementing a STM (Software Transactional Memory) system ...
hawkeye's user avatar
  • 2,581
15 votes
3 answers
2k views

Complexity of edge coloring in planar graphs

3-edge coloring of cubic graphs is $NP$-complete. Four Color Theorem is equivalent to "Every cubic planar bridgeless graphs is 3-edge colorable". What is the complexity of 3-edge coloring of cubic ...
Mohammad Al-Turkistany's user avatar
11 votes
1 answer
265 views

What algorithms/reading matter would you recommend on resolving transactions / read-write locks?

A simplified classical database transaction can be viewed as: reading M items performing some calculation based on those reads writing some N results based on these calculations, which may include ...
Nick Fortescue's user avatar
10 votes
4 answers
767 views

How to know if X and Y have coauthored?

Is there any tool where one can figure out if two people have coauthored or not? Like the tool where one can figure out somebody's Erdos _number_ .
user avatar
93 votes
14 answers
21k views

What kind of mathematical background is needed for complexity theory?

I am currently an undergraduate student, bound to graduate this year. After graduation, I am considering to work towards a TCS master/PhD. I have begun wondering what fields of mathematics are ...
chazisop's user avatar
  • 3,786
15 votes
1 answer
463 views

Graph decompositions for combining "local" functions of vertex labelings

Suppose we want to find $$\sum_x \prod_{ij \in E} f(x_i,x_j)$$ or $$\max_x \prod_{ij \in E} f(x_i,x_j)$$ Where max or sum is taken over all labelings of $V$, product is taken over all edges $E$ for a ...
Yaroslav Bulatov's user avatar
7 votes
0 answers
166 views

Finding the set of paths of smallest cumulated length that cover a given set of patterns

First of all, sorry for this long and maybe not very informative title... Context: Let $G=(V,E)$ be a directed graph, let $v_0 \in V$ be the initial node of paths that I will consider in the graph. ...
Sylvain Peyronnet's user avatar
65 votes
10 answers
12k views

One Stack, Two Queues

background Several years ago, when I was an undergraduate, we were given a homework on amortized analysis. I was unable to solve one of the problems. I had asked it in comp.theory, but no ...
Sadeq Dousti's user avatar
  • 16.5k
12 votes
2 answers
2k views

Is $coNP^{\#P}=NP^{\#P}=P^{\#P}$?

By http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf If $A$ is a PSPACE-complete language, $P^{A}=NP^{A}$. If $B$ is a deterministic polynomial-time oracle, $P^{B}\ne NP^{B}$ (assuming $P\...
Mike Chen's user avatar
  • 709
15 votes
3 answers
4k views

Is there an online-algorithm to keep track of components in a changing undirected graph?

Problem I have an undirected graph (with multi-edges), which will change over time, nodes and edges may be inserted and deleted. On each modification of the graph, I have to update the connected ...
bitmask's user avatar
  • 351
30 votes
6 answers
2k views

Maximum computational power of a C implementation

If we go by the book (or any other version of the language specification if you prefer), how much computational power can a C implementation have? Note that “C implementation” has a technical meaning:...
Gilles 'SO- stop being evil''s user avatar
13 votes
3 answers
4k views

How can DES have 6x4 S-Boxes and still be reversible?

Wouldn't data be lost when mapping 6-bit values to 4-bit values in DES's S-Boxes? If so, how can we reverse it so the correct output appears?
user avatar
26 votes
4 answers
1k views

Is there a non Turing-complete model of computation whose halting problem is undecidable?

I cannot think of any such model, maybe some form of typed lambda calculus? some elementary cellular automaton? This would almost disprove Wolfram's "Principle of Computational Equivalence": ...
didest's user avatar
  • 1,551
6 votes
1 answer
166 views

Non-interesting numbers via resource-bounded properties?

There is an old joke about the smallest non-interesting number being interesting in itself (I have heard it attributed to Richard Hamming). This is then used to justify the argument that every number ...
András Salamon's user avatar
13 votes
0 answers
265 views

Generalizing limit-colimit coincidence to Scott-continuous adjunctions: any uses?

In Abramsky and Jung's 1994 handbook chapter on denotational semantics, after proving that the limit and colimit of expanding sequences exist and coincide, they have the following to say about ...
Neel Krishnaswami's user avatar
1 vote
1 answer
271 views

Another edge partitioning problem on cubic graphs

This question was motivated by a closely related problem An edge partitioning problem on cubic graphs Input: at most cubic graph ( maximum node degree is 3) $G=(V,E)$, a natural number $k$ Question:...
Mohammad Al-Turkistany's user avatar
7 votes
1 answer
1k views

Photo of «Introduction to automata…» by Hopcroft and Ullman '79 cover?

Where can I get the photo of “Introduction to automata theory, languages and computation” by Hopcroft and Ullman '79 (first edition) cover in order to be able to read all the phrases placed on the ...
Artem Pelenitsyn's user avatar
16 votes
1 answer
893 views

Reference for (odd-hole,antihole)-free graphs?

X-free graphs are those that contain no graph from X as an induced subgraph. A hole is a cycle with at least 4 vertices. An odd-hole is a hole with an odd number of vertices. An antihole is the ...
András Salamon's user avatar
1 vote
0 answers
544 views

Algorithm for Minimum Diameter Spanning Tree [closed]

Given a undirected and connected graph G, find a spanning tree whose diameter is the minimum. How to solve this problem
Rambo's user avatar
  • 111
37 votes
5 answers
2k views

Integer multiplication when one integer is fixed

$n$ is a parameter in the problem. For every $n$ we pick a random integer $a_n\in\{2^{n-1},2^{n-1}+1,\dots,2^n-1\}$ where $n\in\{1,2,\dots\}$. Problem: Given $n$ what is the complexity of ...
Turbo's user avatar
  • 12.8k
32 votes
4 answers
4k views

Can a probabilistic Turing machine solve the halting problem?

A computer given an infinite stream of truly random bits is more powerful than a computer without one. The question is: is it powerful enough to solve the halting problem? That is, can a ...
Joey Adams's user avatar
19 votes
1 answer
3k views

Is the dominating set problem restricted to planar bipartite graphs of maximum degree 3 NP-complete?

Does anyone know about an NP-completeness result for the DOMINATING SET problem in graphs, restricted to the class of planar bipartite graphs of maximum degree 3? I know it is NP-complete for the ...
Florent Foucaud's user avatar
29 votes
4 answers
1k views

Maximal classes for which largest independent set can be found in polynomial time?

The ISGCI lists over 1100 classes of graphs. For many of these we know whether INDEPENDENT SET can be decided in polynomial time; these are sometimes called IS-easy classes. I would like to compile ...
András Salamon's user avatar
18 votes
1 answer
596 views

The structure of pathological instances for simplex algorithms

As far as I understand, all know deterministic pivot rules for simplex algorithms have specific inputs on which the algorithm requires exponential time (or at least not polynomial) to find the optimum....
Artem Kaznatcheev's user avatar
1 vote
1 answer
762 views

Is $P^{\#P}=(P^{\#P})^{\#P}$ ?

Intuitively, this equation holds because given the second #P oracle can be omitted since we can always use the first one. More generally, say O is an oracle, is $P^{O}= (P^{O})^{O}$?
Mike Chen's user avatar
  • 709
3 votes
0 answers
193 views

Reference Request: Oracle applications outside cryptography

Oracles have been used to prove results in cryptography where all parties have access to a random oracle instantiated with some cryptographic primitive. I am looking for references to papers that have ...
kryptos's user avatar
  • 460
12 votes
2 answers
624 views

Are Oracles Associative?

This question may have an obvious answer ... but here's the question anyway. Intuitively, it is the following plausible statement - "a machine with a subroutine A which in turn has a subroutine B is ...
gabgoh's user avatar
  • 1,548
10 votes
1 answer
1k views

Quickly finding empty-string producing nonterminals in a CFG

For a given context free language G, we call a nonterminal $A_i$ nullable if $A_i \rightarrow^* \epsilon$, ie we can derive the empty string from $A_i$ after applying a finite number of productions. ...
Alex ten Brink's user avatar
20 votes
1 answer
883 views

Techniques for showing non-derivability in logics and other formal proof systems

In proof systems for classical propositional logic if one want to show that a certain formula $\psi$ is not derivable one simply shows that $\neg\psi$ can be derived (although other techniques ...
Dave Clarke's user avatar
  • 16.7k
11 votes
3 answers
304 views

Learning with "taciturn" oracles

My question is a bit generic, so I'm making up a nice story to justify it. Bear with me if it's not realistic ;-) Story Mr. X, the head of the computer security department at a big company, is a bit ...
Anthony Labarre's user avatar
5 votes
2 answers
909 views

Non-hamiltonian Graphs with unique hamiltonian path between exactly 4 pair of vertices

Need some example graphs which are not Hamiltonian, i.e, does not admit any Hamiltonian cycle, but which have Hamiltonian path. It has Hamiltonian paths between exactly 4 pair of vertices. I have ...
Esha's user avatar
  • 103
7 votes
2 answers
446 views

Energy cost of adiabatic quantum computation

I'm not sure whether this question is completely on-topic, since it is a physics-related question. But I'll ask anyway and apologize if I'm off-topic. In Adiabatic Quantum Computation is Equivalent ...
Antonio Valerio Miceli-Barone's user avatar
38 votes
4 answers
2k views

Interactive proofs for levels of the polynomial hierarchy

We know that if you have a PSPACE machine, it's powerful enough to give an interactive proof of any level the polynomial hierarchy. (And if I remember right, all you need is #P.) But suppose you want ...
Peter Shor 's user avatar
13 votes
2 answers
273 views

complexity of randomized gossiping

The gossiping problem in distributed systems is the following. We have a graph $G$ with $n$ vertices. Each vertex $v$ has a message $m_v$ that must be send to all nodes. Now, my question is in the ...
Sylvain Peyronnet's user avatar
1 vote
1 answer
4k views

Computational power of a 2-PDA [closed]

In our CS class, we have a question about the computational power of PDA's (Push Down Automaton). A 0-PDA (PDA with no stacks) is equivalent to an NFA (Non-deteministic Finite Automaton), while a 1-...
a_m0d's user avatar
  • 113
35 votes
17 answers
2k views

Hardness jumps in computational complexity?

Minimum bandwidth problem is to a find an ordering of graph nodes on integer line that minimizes the largest distance between any two adjacent nodes. A $k$-caterpillar is a tree formed from main path ...
Mohammad Al-Turkistany's user avatar
5 votes
1 answer
504 views

What is the running time of taking a limit?

I'm interested in finding the running time(s) for determining mathematical limits. For instance, $\lim_{x \to 2} \frac{1}{x} = \frac{1}{2}$. I'd like to know more about algorithms for determining ...
Matt Groff's user avatar
  • 2,100
25 votes
4 answers
3k views

Why do equalities between complexity classes translate upwards and not downwards?

Hey Guys, I understand that the padding trick allows us to translate complexity classes upwards - for example $P=NP \rightarrow EXP=NEXP$. Padding works by "inflating" the input, running the ...
gabgoh's user avatar
  • 1,548
14 votes
2 answers
1k views

Difference lists in functional programming

The question What's new in purely functional data structures since Okasaki?, and jbapple's epic answer, mentioned using difference lists in functional programming (as opposed to logic programming), ...
Rob Simmons's user avatar
  • 2,396
8 votes
3 answers
673 views

Proving skip-lists strongly weight-balanced in expectation

Given a skip list of height $n$, what is its expected length, to within a constant (multiplicative) factor? In section 2.2 of Cache-Oblivious B-Trees, Strongly Weight-Balanced Search Trees are ...
jbapple's user avatar
  • 11.2k
16 votes
3 answers
1k views

Is the 3-sphere recognition problem NP-complete?

It is known that determining whether or not a given triangulated 3-manifold is a 3-sphere is in NP, via work by Saul Schleimer in 2004: "Sphere recognition lies in NP" arXiv:math/0407047v1 [math.GT]. ...
Joseph O'Rourke's user avatar
26 votes
2 answers
2k views

Context Sensitive Grammars and Types

1) What, if any, is the relationship between static typing and formal grammars? 2) In particular, would it be possible for a linear bounded automaton to check whether, say, a C++ or SML program was ...
Diogenes Creosote's user avatar
29 votes
2 answers
1k views

Tight Lower bounds on Savitch's theorem

First of all, I apologize in advance for any stupidity. I am by no means an expert on complexity theory (far from it! I am an undergraduate taking my first class in complexity theory) Here's my ...
gabgoh's user avatar
  • 1,548
27 votes
1 answer
915 views

Other applications of Karger-Stein branching amplification?

I just taught the Karger-Stein randomized mincut algorithm in my graduate algorithms class. This is a real algorithmic gem, so I can't not teach it, but it always leaves me frustrated, because I don'...
25 votes
3 answers
2k views

Hardness of approximation - additive error

There is a rich literature and at least one very good book setting out the known hardness of approximation results for NP-hard problems in the context of multiplicative error (e.g. 2-approximation for ...
Simd's user avatar
  • 3,902
22 votes
1 answer
1k views

Binary multiplication and parity convolution

This question is about the relationship between normal multiplication of binary numbers and polynomial multiplication mod 2. To make the question concrete, I would ideally like to know if there is a ...
Simd's user avatar
  • 3,902
5 votes
0 answers
137 views

Integer multiplication where regular Fourier Transform approach would fail to provide best upper bound

I have a problem where multiplication of integers via regular Fourier Transform based multiplication technique would fail to provide best upper bound since the sequences of bits in both integers are ...
Turbo's user avatar
  • 12.8k
2 votes
0 answers
10 views

Complexity of a special matrix

Let $x$, $y$, $z$ $\in \mathbb C$ with $|x| = |y| = |z| = 1$. Has the following matrix (call it $S$) been studied before? \begin{bmatrix} 1 &x &xy &xyz \newline \bar{x} &1 &y &...
Turbo's user avatar
  • 12.8k

15 30 50 per page
1
242 243
244
245 246
256