khaled

That's how you know it is at most NP-Hard.

This in no way says anything about whether it is at least NP-Hard.

If I manage to find a way to turn integer comparison into the SAT problem, that doesn't mean it

suddenly becomes NP-Hard. It just means I have a horrible algorithm for integer comparison.

If you read the links, it shows how scheduling problems are intractable & NP-Hard, how to find that an NP problem is

NP-Hard, what is SAT problem, what Optimization means in general context, and Dynamic Programming (Linear Optimization

through optimal solutions over few variables, which result in the optimal solution for the problem)

- Wikipedia:NSP

- Wikipedia:NP

- Wikipedia:NP-Hard

- Wikipedia:Turing Reduction

- Wikipedia:Optimization

- Wikipedia:Dynamic Programming

Khaled

 

Two things - the question was not optimization, but finding one simple answer; as there seem to be no minor constraints then I think this makes a difference. And I know about the Nurse Scheduling Problem - and I thought at present it was still assumed to be NP-Hard, but not shown to be NP-hard (ie it has not been reduced to a known NP complete in polynomial time). I am not saying it definitely isn't NP - I was curious why you were certain it was

It's good to be curious and it's good to think about it,

These types of problems were already proven NP-Hard in the literature .. and since it can be solved by Constraint Programming,

you can see that it can be reduced to the SAT problem, that how you can know it's NP-Hard,

I think you should avoid using "optimization" in the context of Algorithms since it has a special meaning, I think what you wanted to say

is that the question wasn't about finding an optimal algorithm to solve this problem, but a simple one

Simple answers are a waste of time, either use patterns that may not work, or brute force for years to get the schedule,

I think a simple answer would by reducing the problem to a simpler one that can be solved using Dynamic Programming

Connector,

[math]\sqrt{2} = 1.41421356237309504880168872420969807856967187537694807317667973799... \approx \frac{99}{70}[/math]

The approximation differs from the correct value by less than [math]\frac{1}{10,000}[/math] --Wikipedia

It has a fractional form, you know: [math][1;\bar{2}][/math]

and finally, (personally I don't think you're familiar with this):

Just out of curiosity - how do you know it is NP?

 

Bruteforcing an answer (ie any answer) would seem to me to be polynomial at worse - bruteforcing some "best" answer (with as yet unknown ways of judging merit) might be more likely to be NP - but even so I didn't think anyone could just look at a problem and tell (ie thats half the problem). Or are you able to reduce it to an NP problem?

Despite how trivial scheduling problems may sound,

To be specific, it's NP-hard .. it's a variation of NSP (Nurse Scheduling Problem)

It's usually solved using Constraint Programming or Heuristic Search

I'm not sure of this, but I think that:

By the definition of [math]\mathbb{R}^*[/math]:

[math]\mathbb{R}^* = (\mathbb{R}^+ \cup \mathbb{R}^-) \setminus 0[/math]

[math]\mathbb{R}^* = (\mathbb{R}^+ \cup \mathbb{R}^-) \setminus (\mathbb{R}^+ \cap \mathbb{R}^-)[/math]

Since only 0 satisfy: [math]0 \in \mathbb{R}^+[/math] and [math]0 \in \mathbb{R}^-[/math] we get [math]0 \in (\mathbb{R}^+ \cap \mathbb{R}^-)[/math]

Where [math](\mathbb{R}^+ \cap \mathbb{R}^-) = (\mathbb{R}^+ \cup \mathbb{R}^-) \setminus \mathbb{R}^*[/math]

This problem is just like what DrRocket said, it's a combinatorial problem

I'm not sure, but it seemed similar to knapsack problem, which can be solved using Dynamic Programming (Optimization over few variables)

But this one seem to more complex than a knapsack problem

I could imagine that the number system has two groups, positive numbers and negative numbers, and that they intersect at Zero

Connector,

[latex]\mathbb{R}[/latex] is the set of real numbers,

[latex]\mathbb{R}[/latex] is closed on Multiplication,

we have [math]a \times a = b[/math] where [math]a, b \in \mathbb{R}[/math],

[math]a \times a = b \;\rightarrow\; a^2 = b \;\rightarrow\; a = \sqrt{b}[/math]

Let's substitute b = 2, we get [math]a \times a = 2 \;\rightarrow\; a^2 = 2 \;\rightarrow\; a = \sqrt{2}[/math]

where [math]a \in \mathbb{R}[/math]

I think you are familiar with the term "Relative Address", which is an addressing method, where every reservation have addresses that start from 0 ~ MAX

Where every reservation is given an index (a number) which is used to give the OFFSET,

Example: 4 reservations on a 2 MB RAM, what is the address range for the third ?

Answer:

- Every reservation capacity is ( 2 MB / 4 ) = 512 KB

- MAX = CAPACITY - 1 = 511 (since we start from 0)

- 3rd OFFSET = (3 - 1) * CAPACITY = 2 * 512 KB = 1024 KB

- 3rd Address Range = [OFFSET, OFFSET+MAX] = [1024 KB, 1535 KB] = [1048576, 1571840]

Bootstrap is a process to startup an OS, Bootstrap operates using BIOS

The Bootstrap works on BIOS to load the OS core, kernel, & user interface

With no bootstrap the OS can never startup, so if you lose the bootstrap, you have to re-install that OS,

even though your data and the OS data is still in the hard disk

It's like if the OS is a TV, that can only be operated using a Remote Controller which is the Bootstrap

So even if the TV is still there, it's useless in case you lost the Remote Controller

It depends on what type of website you want to build:

1. Simple website (HTML, CSS, Javascript): a simple website pages .html that are linked with a single style sheet .css, java scripts enable you to do

some tweaks, these websites can be built also through WYSIWYG HTML editors such as FrontPage

2. Master-detail website (HTML, CSS, Javascript, SharePoint\DreamWave\..): using SharePoint\DreamWave\..etc you can build a complete

website, where the shape of your website is designed in a special html page "the master page" .master which contains a detail-containers such

as content-container, now the content pages .html are substituted into the content-container in the master page to the output, it's more like a

formula (master page), and input values (content pages), note also that master-detail websites are dynamic, in SharePoint you can link

your page with a C# or a VB.net code ...

3. Simple Dynamic website (ASP\JSP\PHP, HTML, CSS, Javascript): a dynamic website is one where you can manage users sessions, login

routines, work with the database, ..etc, for example the PHP: .php files represent the website pages, a .php file is basically an HTML

page mixed with PHP code ...

Example (example.html):

<html>
   <head>
       <title>HTML Page Example</title>
   </head>
   <body>
       <div id="header" style="length:100px;width:800px;background-color:red;">header</div>
       <div id="content" style="length:400px;width:800px;background-color:green;">content</div>
       <div id="footer" style="length:40px;width:800px;background-color:blue;">footer</div>
   </body>
</html>

:: Note down here, that we used the same HTML example, but we added PHP code within <? .. ?>

Example (example.php):

<html>
   <head>
       <title>HTML Page Example</title>
   </head>
   <body>
       <div id="header" style="length:100px;width:800px;background-color:red;">header</div>
       <div id="content" style="length:400px;width:800px;background-color:green;">
           <?
               // PHP CODE

               echo "Time: " ;

               // Print Date and Time

               echo strftime ( '%c' ) ;

           ?>
       </div>
       <div id="footer" style="length:40px;width:800px;background-color:blue;">footer</div>
   </body>
</html>

If you are doing this as a business, the website graphical and interactional design and structure is important,

in this case you will need to work with a web graphical designer .. or learn how to design a website using Photoshop, ..etc

and how to trim the website to build the pages\the master page.

So you want to discuss how to build such a website\web-forum with such standards, and information legalization, rights, privacy ?

Because, as a computer scientist, legalizations, rights, privacy, and civilization are related to Law, Politics, & Sociology .. not computer science

How to build a web-forum where people can exchange informations in some ways is related to computer science,

how those people exchange informations or set laws on how they exchange informations is not related to computer science

Best Regards,

khaled, the problem/difference is that on such forum users would decide about extremely important things like legislation which affects them - casual citizens with their causes and billion dollars lobbyists between them. To make it work, it cannot be just a forum like this one, but really deeply well thought for this purpose - designed to handle massive serious discussions and by construction improve their level.

 

Ben, the initial purpose for serious discussion platform was making a step toward direct democracy, so I've placed it there: http://www.scienceforums.net/topic/64141-national-discussion-forum-discuss-then-vote-direct-democracy-using-electronic-signature/

But the discussion was only general about direct democracy there, so I thought that:

- it is much more universal tool, like for working on international computer standards,

- unfortunately even looking very promising Free Internet Act initiative seems to have completely no interest because of current political apathy - I see that going with such initiative from the people has rather no chance now ... but giving politicians tool to improve working on international matters, then expanding it to the people might be more realistic (?),

- and mainly because understanding nuances of designing (and maybe creating) such general tool for serious discussions of huge number of extremely interested persons is rather a task for computer scientists ...

I think this post should be moved to Law or Politics Forum .. since your questions are regarding legalization,

standards, laws, & rights of informations exchanged within a group

the title sound ambiguous to me .. this is how I parsed it "how to design a website, where alot of members can exchange & collaborate informations ?"

We can talk about something, not talk about everything .. what is the point/s you wanna talk about ?

I'm not good in physics, but this is what I know

Time pass always .. maybe it pass faster in a frame than how it pass in another, but in the end at some point,

both frames have passed the same amount of time

So if we can create a Time Capsule which creates a frame that have a high time flow rate .. they won't travel into the future,

they will just experience their life time faster, because their body will pass the same amount of time, in any time flow rate it goes

It's like drinking glasses of beer, weather you drink the beer slower or faster, in the end all men will drink the same amount of beer eventually

Another example is a movie file on your computer, you can play it slower, or 2x faster .. but in all ways, you will witness everything on that movie

Let's share a fun fact: In tennis game Score zero is called 'Love' "Love is Zero", meaning "to play without any wager, for nothing"

.. a Score "Zero to Zero" is called "Love for all"

Source [book]: The Guinness Book of Tennis Facts & Feats and Fifteen Love

Lazy to go google, click here then

The name explains it actually .. design view shows the fields\columns and their data-types, & constraints. data-sheet view shows the data records.

You need to clarify some things:

1. What exactly is your biological data, and how they're represented in your model\system ?

2. What is the problem you are trying to solve, elaborate in essence of input and output.

3. "Random Forest", it's Random Walk

4. "With a single classifier such as Bayesian Network or K-Nearst Neighbors", statistical classifier function

learn (train the model, update the model tables) based on input sample. see Wikipedia:Statistical Classification

I've worked previously on Machine Learning using Markov Chains and Dynamic Programming, if you want to know about it.

No, non-polynomial means non-polynomial. Quite distinct from non-deterministic polynomial (something that would be polynomial given a non-deterministic turing machine). If it turns out that [math]P=NP[/math] non-polynomial would exclude NP.

You are right, and again .. we use it as a short form

Pointing out that I didn't use the exact same jargon as someone else is barely relevant.

I thought you know better than me, it's not about jargons .. solve and calculate have different meanings, verify is not check

Wrong again. Verification will return true if the given input is a solution to the problem. If verification were possible without a test input, then primality testing would be trivial.

Can you revise your informations, checking an answer can be a problem itself you know, it's not using a calculator to check the result of an equation.

The input is the problem, the verification algorithm check if there exist at least 1 solution for the given problem. there is a difference between asking

"are there blue balls in the box ?" (verification), "is this a blue ball ?" (checking), and "bring me a blue ball from the box." (solving)

I side with Schrödinger's hat here. NP means non-deterministic polynomial. By saying "non-polynomial" instead of "non-deterministic polynomial" you are implicitly assume P≠NP. We don't know that yet. That's the whole point of the P versus NP conundrum.

 

There are algorithms that are known not to be polynomial in space or time, even with the aid of an oracle. These fall in a different set of classes than the NP algorithms. Computer scientists who study complexity theory do not use NP to describe these algorithms that are known not to be polynomial in nature. They instead use terms like EXPTIME or EXPSPACE instead.

1. P=NP is an open problem, currently, computer scientists assume that P≠NP since no one have ever came up with a P algorithm to solve an NP problem,

so it's not because I said "non-polynomail" instead of "non-deterministic polynomial", that was a short form we use

2. computer scientists use P and NP in general, technically we use the Big O notation, the classes are literature

3. when I say "verification is a decision problem in which we return TRUE if there exist at least 1 solution for the given problem", don't assume we

make things happens in a flash, the verification itself is a problem too

just a simple question: what if the sword blade is padded by a substance that keep the steel temperature really down, will that make the bindings in the structure stronger ?

You can do it the brute force way, which is NP (takes huge amount of time),

But if you want to do it the smart way, you can use Intelligent Search, Dynamic Programming, or Combinatorial Constraint Satisfaction

[math]NP[/math] Stands for non-deterministic polynomial.

This is a set of problems (factoring is one) where the answer can be checked in polynomial time.

Your note is right, but my definition is not wrong, we use the term "non-polynomial" as a short term in computer science ...

This includes problems in [math]P[/math] where the answer can be calculated (not just checked) in polynomial time as well as problems that have no known solution in polynomial time (but can still be checked that quickly).

(ie. all problems in P are in NP, but it is not known if all problems in NP are in P

 

As Khaled said, it is not known if these problems (the ones that can be checked but not solved quickly) have a fast solution that is undiscovered [math]P=NP[/math] or not [math]P\neq NP[/math]

we use the terms "solve" and "verify\decide" instead of "calculate" and "check", it's an algorithm not an evaluation

Problems can be either solved or verified .. the optimal solution to a problem tell us if it's P, or NP

.. verification of a problem is a decision problem that returns TRUE if there exist a solution, FALSE otherwise

------------------

Note that Problems are solvable or unsolvable .. Solvable Problems are either decidable or undecidable

.. the complexity for verification of a problem is always less than or equal the complexity of solving

[math]P \neq NP[/math]

Here we have [math]P[/math] denotes Polynomial Time Algorithm, and [math]NP[/math] denotes Non-Polynomial Time Algorithm,

-- The statement above is interpreted "there exist no polynomial time algorithm to solve a non-polynomail problem"

A Polynomial Time Algorithm is an algorithm with a Time Complexity that progress slow according to a huge input size [math]N[/math]

A Non-Polynomial Time Algorithm is an algorithm with a Time Complexity that progress fast,

Polynomial Time Complexity examples: [math]O© \;[/math], [math]\; O(log N) \;[/math], [math] \; O(N^c) \;[/math], [math] \; O(\sqrt{N}) \;[/math] ...

These complexities are bounded by polynomials on the form [math]O(\sum_{i=0}^{k}{c_i N^i})[/math]

So basically any complexity that is not bounded by (progress faster than) polynomials as mentioned above, is a Non-Polynomial,

:: It's like saying "anyone that runs slower than Tom is in group Tom, others are in group Non-Tom" .. so "Tom is a bound for members of group Tom".

Non-Polynomial Time Complexity examples: [math] \; c^N \;[/math], [math] \; N^N \;[/math], [math] \; N ! \;[/math] ...

-- where [math]c[/math] is a constant,

Note: the above definitions are unofficial, they are to help understand.

Also notice that the question: [math]is \;\; P \; = \; NP[/math] is still an open problem in Computer Science and Mathematical Logic,

which ask if there exist a polynomial time algorithm that can solve an NP problem