# All Questions

1,411 questions
Filter by
Sorted by
Tagged with
1answer
164 views

### Any result connecting an NP-complete problem with slight super-polynomial time?

Helo everybody, is there any result or research that connects some $NP$-complete problem with only slightly super-polynomial (strongly sub-exponential) time? This would not necessarily involve ...
1answer
231 views

### Many-one reduction from inequality problem to equality problem

Let the k-inequality-MIS problem be the decision problem whether an arbitrary graph $G=(V, E)$ contains a maximal independent set of at least size $k$, that is the corresponding language is: \...
0answers
78 views

### Generalizing a set of positive and negative examples through DFAs [duplicate]

Possible Duplicate: Is finding the minimum regular expression an NP-complete problem? Let $\Sigma$ be an alphabet. Let $P$ and $N$ (the set of positive and negative examples) be two disjoint ...
0answers
444 views

### Complexity Theory conferences? [closed]

What are the most significant annual Complexity Theory conferences? Rules: One conference per answer Include a link to the conference
0answers
58 views

### Specification language for specifying both Objects and Primitive data types

I am looking for an specification language, which supports both primitive data types and objects. I already know about Object-Z. But I am wondering if there is any other Specification language that I ...
1answer
497 views

### Find the maximum flux path between two nodes [closed]

Given a graph $G$ and two vertices $s$ and $t$, I want the maximum flux path from $s$ to $t$.That is, imagine $G$ to be a flow network with capacities on the edges. I want to find a single path that ...
1answer
560 views

### What does “number of inputs to each neuron” mean in Neural Network terms? [closed]

I am reading about a Neural Networks project that has some data like this I am new to this, and though I think I understand what a 3:1 network mean, I do not understand what number of inputs (to each ...
1answer
840 views

### Algorithm: Find the first k longest substrings between two similar strings

Consider two strings, S and T. Find the first k longest common non-overlapping substrings of S and T.
1answer
1k views

### What's wrong with my linear programming formulation of longest path? [closed]

I have a directed graph which has cycles. Each edge has a positive weight. Now given two vertices $u$ and $v$, I want to find the longest simple path from $u$ to $v$. Simple means the path has no ...
1answer
747 views

### Is there any proof that a network made of Turing machines can't solve the halting problem? [closed]

My question points to the fact that Turing machines are isolated by definition. But what if they can send and receive information from/to other Turing machines? What if they can be "interrupted" at ...
1answer
239 views

### Can on every instance P = NP? [closed]

I want to ask a question concerning some aspects of the P vs. NP problem. NOTE: Possibly by "popular" standards i am a crank (i tend towards P=NP), but lets focus on the issue (please with a grain of ...

15 30 50 per page